The Complexity of Embedding of Acyclic Graphs into Grids with Minimum Congestion

スポンサーリンク

概要

• 論文の詳細を見る

• It is known that the problem of determining, given a planar graph G and integers m and n, whether there exists a congestion-1 embedding of G into a two dimensional m×n-grid is NP-complete. In this paper, we show that the problem is still NP-complete if G is restricted to an acyclic graph.

• 社団法人電子情報通信学会の論文
• 2000-11-25

著者

• Matsubayashi Akira

  Faculty Of Engineering Kanazawa University

• Matsubayashi Akira

  The Faculty Of Engineering Utsunomiya University

• Matsubayashi Akira

  Faculty Of Engineering Tokyo Institute Of Technology

• Yokota Masaya

  The Faculty Of Engineering Utsunomiya University

関連論文

• 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

スポンサーリンク