2001年5月
On the complexity of minimum congestion embedding of acyclic graphs into ladders
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
- 巻
- E84A
- 号
- 5
- 開始ページ
- 1218
- 終了ページ
- 1226
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
is known that the problem of determining, given a planar graph C: and an integer m; whether there exists a congestion-1 embedding of G' into an m x k-grid is NP-compiete for a fixed integer k greater than or equal to 3. It is also known that the problem for k = 3 is NP-complete even if G is restricted to an acyclic graph. The complexity of the problem for ic = 2 was left open. In this paper, we show that for k = 2, the problem can be solved in polynomial time if G is restricted to a tree, while the problem is NP-complete even if G is restricted to an acyclic graph.
- リンク情報
- ID情報
-
- ISSN : 1745-1337
- Web of Science ID : WOS:000168658500017