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

Fekete, Sandor P. and Khuller, Samir and Klemmstein, Monika and Raghavachari, Balaji and Young, Neal (1996) A network-flow technique for finding low-weight bounded-degree spanning trees.
Published In: Integer programming and combinatorial optimization : 5th International IPCO Conference, Vancouver, British Columbia, Canada, June 3 - 5, 1996 ; proceedings, Lecture notes in computer science. 1084 Springer 1996, pp. 105-117.


Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, we consider the problem of computing a low weight spanning tree such that the degree of each vertex is at most its specified bound. In particular, we give efficient algorithms for modifying a given spanning tree T to meet the degree constraints. These algorithms are optimal in the following sense: We show that in the worst case, the weight of the tree increases by at most a factor of 2 - minBig{frac{goal(v)-2}{degree_T(v)-2} : degree_{T}(v)>2Big}, where goal(v) ge 2 is the desired degree of vertex v and degree_T(v) is the initial degree; we also show that this factor is best possible. We conclude the paper by discussing geometric aspects of the problem.

Download: [img] Postscript - Preprinted Version
Download (283kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr95-208
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 10:10
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/208