WEKO3
インデックスリンク
アイテム
Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion
http://hdl.handle.net/2297/19124
http://hdl.handle.net/2297/1912443086d76-1b56-4176-ace0-e7717d6d01aa
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-MATSUBAYASHI-A-2938.pdf (1.3 MB)
|
|
| Item type | 会議発表論文 / Conference Paper(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2017-10-03 | |||||
| タイトル | ||||||
| タイトル | Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||
| 資源タイプ | conference paper | |||||
| 著者 |
Matsubayashi, Akira
× Matsubayashi, Akira |
|||||
| 提供者所属 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 金沢大学理工研究域電子情報学系 | |||||
| 書誌情報 |
Proceedings - IEEE International Symposium on Circuits and Systems 巻 2009, p. 2938-2941, 発行日 2009-01-01 |
|||||
| 出版者 | ||||||
| 出版者 | IEEE = Institute of Electrical and Electronics Engineers | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | We study the problem of embedding a guest graph into an optimally-sized grid with minimum edge-congestion. Based on a wellknown notion of graph separator, we prove that any guest graph can be embedded with a smaller edge-congestion as the guest graph has a smaller separator, and as the host grid has a higher dimension. Our results imply the following: An N-node planar graph with maximum node degree Δ can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Δ2 logN) if d = 2, O(Δ2 log logN) if d = 3, and O(Δ2) otherwise. An N-node graph with maximum node degree Δ and a treewidth O(1), such as a tree, an outerplanar graph, and a series-parallel graph, can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Δ) for d ≥ 2. | |||||
| 著者版フラグ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
