A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
Authors:
- J. KönemannJKJ. Könemann
- R. RaviRRR. Ravi
- 1 January 2002
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 31 (6) , 1783-1793
Abstract
In this paper, we present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. In this problem, we are given an undirected graph, a nonnegative cost function on the edges, and a positive integer B * , and the goal is to find a minimum-cost spanning tree T with maximum degree at most B * . In an n-node graph, our algorithm finds a spanning tree with maximum degree O(B * +logn) and cost O(opt B * ), where opt B * is the minimum cost of any spanning tree whose maximum degree is at most B * . Our algorithm uses ideas from Lagrangean duality. We show how a set of optimum Lagrangean multipliers yields bounds on both the degree and the cost of the computed solution.Keywords
This publication has 13 references indexed in Scilit:
- Degree-constrained multicasting in point-to-point networks2002
- Bicriteria Network Design ProblemsJournal of Algorithms, 1998
- A reliable multicast framework for light-weight sessions and application level framingIEEE/ACM Transactions on Networking, 1997
- Low-Degree Spanning Trees of Small WeightSIAM Journal on Computing, 1996
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner TreesJournal of Algorithms, 1995
- Approximating the Minimum-Degree Steiner Tree to within One of OptimalJournal of Algorithms, 1994
- A copy network with shared buffers for large-scale multicast ATM switchingIEEE/ACM Transactions on Networking, 1993
- On the spanning tree polyhedronOperations Research Letters, 1989
- Integer and Combinatorial Optimization1988
- Optimum branchingsJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967