A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
复制标题
A (1+ε)-将低公路维数图嵌入有界树宽图
DOI：
10.1137/16m1067196
复制
发表时间：
2015
影响因子：
3.7
通讯作者：
Ian Post
中科院分区：
文献类型：
--
作者：
A. Feldmann;W. Fung;J. Könemann;Ian Post
[Abraham et al., SODA 2010] 中引入了有界高速公路维度图作为交通网络模型。我们证明任何这样的图都可以嵌入到有界树宽图上的分布中，并且失真度任意小。更具体地说，如果 G 的高速公路维数是常数，我们将展示如何随机计算输入图 G 的最短路径度量的子图，其具有以下两个属性：它使 G 的距离在期望中扭曲 \(1+{\varepsilon }\) 因子，并且树宽在 G 的纵横比上是多对数的。特别是，这个结果意味着针对交通运输中自然出现的许多优化问题的拟多项式时间近似方案网络，包括旅行推销员、斯坦纳树和设施位置。
Graphs with bounded highway dimension were introduced in [Abraham et al., SODA 2010] as a model of transportation networks. We show that any such graph can be embedded into a distribution over bounded treewidth graphs with arbitrarily small distortion. More concretely, if the highway dimension of G is constant we show how to randomly compute a subgraph of the shortest path metric of the input graph G with the following two properties: it distorts the distances of G by a factor of \(1+{\varepsilon }\) in expectation and has a treewidth that is polylogarithmic in the aspect ratio of G. In particular, this result implies quasi-polynomial time approximation schemes for a number of optimization problems that naturally arise in transportation networks, including Travelling Salesman, Steiner Tree, and Facility Location.
DOI：
10.1016/j.tcs.2016.07.003
发表时间：
2013-07
期刊：
--
影响因子：
--
作者：
Reinhard Bauer;Tobias Columbus;Ignaz Rutter;D. Wagner
通讯作者：
Reinhard Bauer;Tobias Columbus;Ignaz Rutter;D. Wagner