### Abstract

Given 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 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 previous algorithm. 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{(d(v) - 2)/(deg_{T}(v) - 2):deg_{T}(v) > 2}, where deg_{T}(v) is the initial degree of v. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds for any algorithm at all, then it also holds for the given algorithm. 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 with factors less than 2 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 Salesman path and a minimum spanning tree can be arbitrarily close to 2.

Original language | English (US) |
---|---|

Pages (from-to) | 310-324 |

Number of pages | 15 |

Journal | Journal of Algorithms |

Volume | 24 |

Issue number | 2 |

DOIs | |

State | Published - Aug 1997 |

### ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees'. Together they form a unique fingerprint.

## Cite this

*Journal of Algorithms*,

*24*(2), 310-324. https://doi.org/10.1006/jagm.1997.0862