論文

査読有り
2015年4月

Separator-based graph embedding into multidimensional grids with small edge-congestion

DISCRETE APPLIED MATHEMATICS
  • Akira Matsubayashi

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.

リンク情報
DOI
https://doi.org/10.1016/j.dam.2014.11.024
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000352171600014&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/j.dam.2014.11.024
  • ISSN : 0166-218X
  • eISSN : 1872-6771
  • Web of Science ID : WOS:000352171600014

エクスポート
BibTeX RIS