## A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees

##### View/Open

##### Date

1998-10-15##### Author

Fekete, Sandor P.

Khuller, Samir

Klemmstein, Monika

Raghavachari, Balaji

Young, Neal

##### Metadata

Show full item record##### Abstract

Given a graph with edge weights satisfying the triangle inequality,
and a degree bound for each vertex,
the problem of computing a low weight spanning tree
such that the degree of each vertex is at most its specified bound
is considered.
In particular, modifying a given spanning tree $T$
using {\em adoptions} to meet the degree constraints is considered.
A novel network-flow based algorithm for finding
a good sequence of adoptions is introduced.
The method yields a better performance guarantee
than any previously obtained.
Equally importantly, it yields the best performance guarantee among
the class of algorithms that rely solely on the topology and edge
weights of the given tree.
The performance guarantee is the following.
If the degree constraint $d(v)$ for each $v$ is at least $2$,
the algorithm is guaranteed to find a tree whose weight is at most
the weight of the given tree times
$2 - \min\{\frac{d(v)-2}{\D_T(v)-2} : \D_T(v)>2\},$
where $D_T(v)$ is the initial degree of $v$.
Examples are provided in which no lighter tree
meeting the degree constraint exists.
Linear-time algorithms are provided with the same worst-case
performance guarantee.
Choosing $T$ to be a minimum spanning tree yields approximation
algorithms for the general problem on geometric graphs with
distances induced by various $L_p$ norms.
Finally, examples of Euclidean graphs are provided in which
the ratio of the lengths of an optimal Traveling Salesperson path
and a minimum spanning tree can be arbitrarily close to~2.
(Also cross-referenced as UMIACS-TR-95-95)

University of Maryland, College Park, MD 20742-7011 (301)314-1328.

Please send us your comments.