On the Complexity of Minimum Congestion Embedding of Acyclic Graphs into Ladders

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2001-05-01

著者

• Matsubayashi Akira

  Faculty Of Engineering Kanazawa University

• Matsubayashi Akira

  The Faculty Of Engineering Utsunomiya University

• Matsubayashi Akira

  Faculty Of Engineering Tokyo Institute Of Technology

関連論文

• On the Complexity of Embedding of Graphs into Grids with Minimum Congestion (Special Section on Discrete Mathematics and Its Applications)
• VLSI Layout of Trees into Grids of Minimum Width
• A Linear Time Algorithm for Constructing Proper-Path-Decomposition of Width Two
• The Complexity of Embedding of Acyclic Graphs into Grids with Minimum Congestion
• On the Complexity of Minimum Congestion Embedding of Acyclic Graphs into Ladders
• Minimum Congestion Embedding of Complete Binary Trees into Tori

スポンサーリンク