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

dc.contributor.authorFekete, Sandor P.en_US
dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorKlemmstein, Monikaen_US
dc.contributor.authorRaghavachari, Balajien_US
dc.contributor.authorYoung, Nealen_US
dc.date.accessioned2004-05-31T22:34:56Z
dc.date.available2004-05-31T22:34:56Z
dc.date.created1995-12en_US
dc.date.issued1998-10-15en_US
dc.description.abstractGiven 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)en_US
dc.format.extent514829 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/762
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3538en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-95-95en_US
dc.titleA Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Treesen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3538.ps
Size:
502.76 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3538.pdf
Size:
261.84 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3538.ps