On the Complexity of Embedding of Graphs into Grids with Minimum Congestion (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m×n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in a k×n grid with unit congestion for any fixed integer k≧3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2×∞ grid with unit congestion, and show that G satisfying the condition is embeddable in a 2×∞|V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2×∞ grid with unit congestion.
- 社団法人電子情報通信学会の論文
- 1996-04-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
-
UENO Shuichi
Faculty of Engineering, Tokyo Institute of Technology
-
Ueno Shuichi
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
- Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two
- Universal Graphs for Graphs with Bounded Path-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