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

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

Download: |
Postscript
- Preprinted Version
Download (283kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

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 |