Optimizing the Degree of Minimum Weight Spanning Trees
Author | : Cornell University. Dept. of Computer Science |
Publisher | : |
Total Pages | : 5 |
Release | : 1993 |
ISBN-10 | : OCLC:255884604 |
ISBN-13 | : |
Rating | : 4/5 ( Downloads) |
Download or read book Optimizing the Degree of Minimum Weight Spanning Trees written by Cornell University. Dept. of Computer Science and published by . This book was released on 1993 with total page 5 pages. Available in PDF, EPUB and Kindle. Book excerpt: 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[superscript]{*} + logn)$ where $\delta[superscript]{*}$ 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[superscript]{*} + 1)$, where $k$ is the number of distinct weights in the graph. Finding the exact minimum is NP-hard.