2001年5月1日
On the Complexity of Minimum Congestion Embedding of Acyclic Graphs into Ladders
IEICE transactions on fundamentals of electronics, communications and computer sciences
- 巻
- 84
- 号
- 5
- 開始ページ
- 1218
- 終了ページ
- 1226
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- 電子情報通信学会
It is known that the problem of determining, given a planar graph G and an integer m, whether there exists a congestion-1 embedding of G into an m×k-grid is NP-complete for a fixed integer k≥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 k=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.
- リンク情報
-
- CiNii Articles
- http://ci.nii.ac.jp/naid/110003208924
- CiNii Books
- http://ci.nii.ac.jp/ncid/AA10826239
- URL
- http://hdl.handle.net/2297/3534
- ID情報
-
- ISSN : 0916-8508
- CiNii Articles ID : 110003208924
- CiNii Books ID : AA10826239