TY - JOUR

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

AU - Fekete, Sándor P.

AU - Khuller, Samir

AU - Klemmstein, Monika

AU - Raghavachari, Balaji

AU - Young, Neal

N1 - Funding Information:
*A preliminary version of this paper appeared in ``Proceedings of the 5th International Integer Programming and Combinatorial Optimization Conference IPCO), June 1996,'' pp. 105—117. ²E-mail: sandor@zpr.uni-koeln.de. ³Research supported by NSF Research Initiation Award CCR-9307462 and an NSF CAREER Award CCR-9501355. E-mail: samir@cs.umd.edu. §E-mail: mklemmst@zpr.uni-koeln.de. 5Research supported in part by NSF Research Initiation Award CCR-9409625. E-mail: rbk@utdallas.edu.

PY - 1997/8

Y1 - 1997/8

N2 - 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 previous algorithm. 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{(d(v) - 2)/(degT(v) - 2):degT(v) > 2}, where degT(v) is the initial degree of v. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds for any algorithm at all, then it also holds for the given algorithm. 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 with factors less than 2 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 Salesman path and a minimum spanning tree can be arbitrarily close to 2.

AB - 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 previous algorithm. 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{(d(v) - 2)/(degT(v) - 2):degT(v) > 2}, where degT(v) is the initial degree of v. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds for any algorithm at all, then it also holds for the given algorithm. 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 with factors less than 2 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 Salesman path and a minimum spanning tree can be arbitrarily close to 2.

UR - http://www.scopus.com/inward/record.url?scp=0038192551&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038192551&partnerID=8YFLogxK

U2 - 10.1006/jagm.1997.0862

DO - 10.1006/jagm.1997.0862

M3 - Article

AN - SCOPUS:0038192551

VL - 24

SP - 310

EP - 324

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 2

ER -