論文

2001年5月

On the complexity of minimum congestion embedding of acyclic graphs into ladders

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
  • A Matsubayashi

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.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000168658500017&DestApp=WOS_CPL
ID情報
  • ISSN : 1745-1337
  • Web of Science ID : WOS:000168658500017

エクスポート
BibTeX RIS