Optimizing the Degree of Minimum Weight Spanning Trees
Permanent Link(s)
Collections
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-04
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1338
Type
technical report