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 (1997) A network-flow technique for finding low-weight bounded-degree spanning trees.
Published in: Journal of Algorithms Vol. 24 (2). pp. 310-324.


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr95-208a
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 09:34
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/208001