# 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.

## Abstract

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.

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 |