A Network-Flow Technique for Finding Low-Weight

Bounded-Degree Spanning Trees

S?andor P. Fekete ?y Samir Khuller z Monika Klemmstein? x

Balaji Raghavachari { Neal Young k

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 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
n d(v)?2
degT (v)?2 : degT (v) > 2
o
; where degT (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 Lp 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.

?Center for Parallel Computing, Universitat zu Koln, D-50923 Koln, Germany.
yE-Mail: sandor@zpr.uni-koeln.de.
zComputer Science Department and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742. Research supported by NSF Research Initiation Award CCR-9307462 and an NSF CAREER Award CCR-9501355. E-mail : samir@cs.umd.edu.
xE-Mail: mklemmst@zpr.uni-koeln.de.
{Department of Computer Science, The University of Texas at Dallas, Box 830688, Richardson, TX 75083-0688. Research supported in part by NSF Research Initiation Award CCR-9409625. E-mail : rbk@utdallas.edu. kDept. of Computer Science, Dartmouth College, Hanover NH 03755-3510. Part of this research was done while at School of ORIE, Cornell University, Ithaca NY 14853 and supported by ?Eva Tardos' NSF PYI grant DDM-9157199. E-mail : ney@cs.dartmouth.edu.