MISC

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
  • MATSUBAYASHI Akira

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

エクスポート
BibTeX RIS