## 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 previously obtained. 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 our algorithm. The performance guarantee is the following.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 (formula presented) where deg_{T}(v) is the initial degree of v. 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 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) |
---|---|

Title of host publication | Integer Programming and Combinatorial Optimization - 5th International IPCO Conference, 1996 Proceedings |

Editors | William H. Cunningham, S.Thomas McCormick, Maurice Queyranne |

Publisher | Springer Verlag |

Pages | 105-117 |

Number of pages | 13 |

ISBN (Print) | 3540613102, 9783540613107 |

DOIs | |

State | Published - 1996 |

Event | 5th International Conference Integer Programming and Combinatorial Optimization, IPCO 1996 - Vancouver, Canada Duration: Jun 3 1996 → Jun 5 1996 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1084 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 5th International Conference Integer Programming and Combinatorial Optimization, IPCO 1996 |
---|---|

Country/Territory | Canada |

City | Vancouver |

Period | 6/3/96 → 6/5/96 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)