Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees
Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees
复制标题
查看树的年轮：最小失真嵌入树中
DOI：
10.1137/1.9781611975482.146
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Raichel, Benjamin
中科院分区：
文献类型：
--
作者：
Nayyeri, Amir;Raichel, Benjamin
本文给出了一个求n点度量空间（X，dX）到顶点集为X的树的最小失真嵌入的（1 +ε）近似算法.该算法的运行时间为n2·（Δ/ε）（O（δopt/ε））2λ +1，其参数分别为X的扩展度Δ、嵌入到树中的最小可能失真δopt和X的二倍维数λ.因此，我们得到了一个PTAS，只要δ ops是常数，X是一个具有多项式有界展度的有限倍度量空间，例如，常维欧氏空间中具有多项式有界展度的点集.在允许Steiner顶点的情况下，我们的算法是一个常数因子近似，并且给出了一个类似的（1 +ε）近似算法，用于寻找（X，dX）的最大拉伸最小的树。我们的算法的运行时间保持不变，除了δ opt必须被解释为X的任何生成树的最小伸展。最后，我们将我们的树扩张算法推广到一个计算加权图的最小拉伸树扩张的（1 +ε）近似算法，其中除了上述其他参数外，运行时间还被参数化为最大度。特别是，我们得到了一个PTAS计算最小拉伸树的加权图，多项式有界的蔓延，常数倍维数，常数最大程度，当树的拉伸常数存在。
We describe a (1 +ε) approximation algorithm for finding the minimum distortion embedding of ann-point metric space, (X, dX), into a tree with vertex setX. The running time of our algorithm isn2· (Δ/ε)(O(δopt/ε))2λ+1parameterized with respect to the spread ofX, denoted by Δ, the minimum possible distortion for embeddingXinto any tree, denoted byδopt, and the doubling dimension ofX, denoted by λ. Hence we obtain a PTAS, providedδoptis a constant andXis a finite doubling metric space with polynomially bounded spread, for example, a point set with polynomially bounded spread in constant dimensional Euclidean space. Our algorithm implies a constant factor approximation with the same running time when Steiner vertices are allowed.Moreover, we describe a similar (1 +ε) approximation algorithm for finding a tree spanner of (X, dX) that minimizes the maximum stretch. The running time of our algorithm stays the same, except thatδoptmust be interpreted as the minimum stretch of any spanning tree ofX. Finally, we generalize our tree spanner algorithm to a (1 +ε) approximation algorithm for computing a minimum stretch tree spanner of a weighted graph, where the running time is parameterized with respect to the maximum degree, in addition to the other parameters above. In particular, we obtain a PTAS for computing minimum stretch tree spanners of weighted graphs, with polynomially bounded spread, constant doubling dimension, and constant maximum degree, when a tree spanner with constant stretch exists.
登录
查看更多内容
系统发育树估计教程
DOI：
--
发表时间：
1999
期刊：
Intelligent Systems in Molecular Biology
影响因子：
--
作者：
Junhyong Kim
通讯作者：
Junhyong Kim
实线上的拟合点及其在RH测绘中的应用
影响因子：
1.7
作者：
J. Håstad;Lars Ivansson;J. Lagergren
通讯作者：
J. Lagergren
影响因子：
1.1
作者：
Ioannis Papoutsakis
通讯作者：
Ioannis Papoutsakis
Arrow 分布式目录的低复杂性变体
DOI：
--
发表时间：
2001
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
D. Peleg;Eilon Reshef
通讯作者：
Eilon Reshef
计算最小扩张生成树是 NP 困难的
DOI：
--
发表时间：
2007
期刊：
Computational geometry
影响因子：
--
作者：
O. Cheong;H. Haverkort;Mira Lee
通讯作者：
Mira Lee