Loading...
Please wait, while we are loading the content...
Similar Documents
Spanning trees short or small (1994)
| Content Provider | CiteSeerX |
|---|---|
| Author | Ravi, R. Sundaram, R. Marathe, M. V. Rosenkrantz, D. J. Ravi, S. S. |
| Description | We study the problem of nding small trees. Classical network design problems are considered with the additional constraint that only a specied 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 2 p k for the general edge-weighted case and O(k 1=4) for the case of points in the plane. Polynomial-time exact solutions are also presented for the class of decomposable 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 nding short trees, and more generally, that of nding networks with minimum diameter. A simple technique is used to provide a polynomial-time solution for nding k-trees of minimum diameter. We identify easy and hard problems arising in nding short networks using a framework due to T. C. Hu. Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms |
| File Format | |
| Language | English |
| Publisher Date | 1994-01-01 |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
