JavaScript is disabled for your browser. Some features of this site may not work without it.
Optimizing the Degree of Minimum Weight Spanning Trees

Author
Fischer, Ted
Abstract
This paper presents two algorithms to construct minimum weight spanning trees with approximately minimum degree. The first method gives a spanning tree whose maximum degree is $O(\delta^{*} + logn)$ where $\delta^{*}$ is the minimum possible, and $n$ is the number of vertices. The second method gives a spanning tree of degree no more than $k \cdot (\delta^{*} + 1)$, where $k$ is the number of distinct weights in the graph. Finding the exact minimum is NP-hard.
Date Issued
1993-04Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1338
Type
technical report