Spanning trees short or small
Spanning trees short or small
复制标题
DOI：
10.1137/s0895480194266331
复制
发表时间：
1994-01
期刊：
影响因子：
--
通讯作者：
R. Ravi;Ravi Sundaram;M. Marathe;D. Rosenkrantz;S. Ravi
中科院分区：
文献类型：
--
作者：
R. Ravi;Ravi Sundaram;M. Marathe;D. Rosenkrantz;S. Ravi
我们研究寻找小树的问题。经典的网络设计问题考虑了附加的约束，即在解中只需要连接指定数目的k个节点。一个典型的例子是kMST问题，在这个问题中，我们要求在一个边加权图中有一棵至少横跨k个节点的最小权树。我们证明了即使对于欧几里得平面上的点，kMST问题也是NP难的。对于一般的边加权情况，我们给出了性能比为2v/的近似算法，对于平面上点的情况，性能比为O(K1/4)。文中还给出了一类树宽有界图的多项式时间精确解，包括树、串并图和有界带宽图，以及欧氏平面上凸域边界上的点。我们还研究了寻找短树的问题，更广泛地说，是寻找具有最小直径的网络的问题。使用一种简单的技术来提供寻找最小直径的k-树的多项式M-时间解。我们确定了在使用T.C.Hu的框架寻找短网络时出现的容易和困难的问题。
We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number k of nodes are required to be connected in the solution. A prototypical example is the kMST problem in which we require a tree of minimum weight spanning at least k nodes in an edge-weighted graph. We show that the kMST problem is NP-hard even for points in the Euclidean plane. We provide approximation algorithms with performance ratio 2v/ for the general edge-weighted case and O(k1/4) for the case of points in the plane. Polynomial-time exact solutions are also presented for the class of treewidth-bounded graphs, which includes trees, series-parallel graphs, and bounded bandwidth graphs, and for points on the boundary of a convex region in the Euclidean plane. We also investigate the problem of finding short trees and, more generally, that of finding networks with minimum diameter. A simple technique is used to provide a polynomiM-time solution for finding k-trees of minimum diameter. We identify easy and hard problems arising in finding short networks using a framework due to T. C. Hu.