Optimizing the Degree of Minimum Weight Spanning Trees

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.