A network-flow technique for finding low-weight bounded-degree spanning trees

Sándor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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 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 our algorithm. 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 (formula presented) 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 Salesman path and a minimum spanning tree can be arbitrarily close to 2.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 5th International IPCO Conference, 1996 Proceedings
EditorsWilliam H. Cunningham, S.Thomas McCormick, Maurice Queyranne
PublisherSpringer Verlag
Pages105-117
Number of pages13
ISBN (Print)3540613102, 9783540613107
StatePublished - Jan 1 1996
Event5th International Conference Integer Programming and Combinatorial Optimization, IPCO 1996 - Vancouver, Canada
Duration: Jun 3 1996Jun 5 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1084
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Conference Integer Programming and Combinatorial Optimization, IPCO 1996
CountryCanada
CityVancouver
Period6/3/966/5/96

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'A network-flow technique for finding low-weight bounded-degree spanning trees'. Together they form a unique fingerprint.

  • Cite this

    Fekete, S. P., Khuller, S., Klemmstein, M., Raghavachari, B., & Young, N. (1996). A network-flow technique for finding low-weight bounded-degree spanning trees. In W. H. Cunningham, S. T. McCormick, & M. Queyranne (Eds.), Integer Programming and Combinatorial Optimization - 5th International IPCO Conference, 1996 Proceedings (pp. 105-117). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1084). Springer Verlag.