Spanning trees short or small

Details Spanning trees short or small Spanning trees short or small

1994-09-21

arxiv.org/abs/math/9409222v1

Mathematics

Combinatorics

27 pages

Scientific paper

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 $k$MST problem in which we require a tree of minimum weight spanning at least $k$ nodes in an edge-weighted graph. We show that the $k$MST problem is NP-hard even for points in the Euclidean plane. We provide approximation algorithms with performance ratio $2\sqrt{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 finding short trees, and more generally, that of finding networks with minimum diameter. A simple technique is used to provide a polynomial-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.

Affiliated with

Also associated with

No associations

Rating

Spanning trees short or small does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spanning trees short or small, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning trees short or small will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-635591