2015年4月
Separator-based graph embedding into multidimensional grids with small edge-congestion
DISCRETE APPLIED MATHEMATICS
- 巻
- 185
- 号
- 開始ページ
- 119
- 終了ページ
- 137
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.dam.2014.11.024
- 出版者・発行元
- ELSEVIER SCIENCE BV
We study the problem of embedding a guest graph with minimum edge-congestion into a multidimensional grid with the same size as that of the guest graph. Based on a well-known notion of graph separators, we show that an embedding with a smaller edge-congestion can be obtained if the guest graph has a smaller separator, and if the host grid has a higher but constant dimension. Specifically, we prove that any graph with N nodes, maximum node degree Delta, and with a node-separator of size s, where s is a function such that s(n) = 0(n(alpha)) with 0 <= alpha < 1, can be embedded into a grid of a fixed dimension d >= 2 with at least N nodes, with an edge-congestion of 0(Delta) if d > 1/(1 - a), 0(Delta log N) if d = 1/(1 - alpha), and 0(Delta N alpha-1+1/d) if d < 1/(1 - alpha). This edge-congestion achieves constant ratio approximation if d > 1/(1 - alpha), and matches an existential lower bound within a constant factor if d <= 1/(1 - alpha). Our result implies that if the guest graph has an excluded minor of a fixed size, such as a planar graph, then we can obtain an edge-congestion of 0(Delta log N) for d = 2 and 0(Delta) for any fixed d >= 3. Moreover, if the guest graph has a fixed treewidth, such as a tree, an outerplanar graph, and a series-parallel graph, then we can obtain an edge-congestion of 0(Delta) for any fixed d >= 2. To design our embedding algorithm, we introduce edge-separators bounding extension, such that in partitioning a graph into isolated nodes using edge-separators recursively, the number of outgoing edges from a subgraph to be partitioned in a recursive step is bounded. We present an algorithm to construct an edge-separator with extension of 0(Delta(alpha)) from a node-separator of size 0(n(alpha)). (c) 2014 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.dam.2014.11.024
- ISSN : 0166-218X
- eISSN : 1872-6771
- Web of Science ID : WOS:000352171600014