Line-Distortion, Bandwidth and Path-Length of a Graph

详细信息    查看全文

• 作者：Feodor F. Dragan ; Ekkehard Köhler ; Arne Leitert
• 关键词：Graph algorithms ; Approximation algorithms ; Minimum line ; distortion ; Minimum bandwidth ; Robertson–Seymour’s path ; decomposition ; Path ; length ; AT ; free graphs
• 刊名：Algorithmica
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：77
• 期：3
• 页码：686-713
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
• 出版者：Springer US
• ISSN：1432-0541
• 卷排序：77

文摘

For a graph \(G=(V,E)\) the minimum line-distortion problem asks for the minimum k such that there is a mapping f of the vertices into points of the line such that for each pair of vertices x, y the distance on the line \(|f(x) - f(y)|\) can be bounded by the term \(d_G(x, y)\le |f(x)-f(y)|\le k \, d_G(x, y)\), where \(d_G(x, y)\) is the distance in the graph. The minimum bandwidth problem minimizes the term \(\max _{uv\in E}|f(u)-f(v)|\), where f is a mapping of the vertices of G into the integers \(\{1, \ldots , n\}\). We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a Robertson–Seymour’s path-decomposition. The length of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The path-length of a graph is the minimum length over all its path-decompositions. In particular, we show:there is a simple polynomial time algorithm that embeds an arbitrary unweighted input graph G into the line with distortion \(\mathcal{O}(k^2)\), where k is the minimum line-distortion of G;