CSAIL Event Calendar: Previous Series
Minimum Bounded Degree Spanning Trees
Speaker: Michel Goemans , MIT
Relevant URL: http://theory.csail.mit.edu/toc-seminars/
The minimum spanning tree is one the most fundamental combinatorial optimization problems, and its efficient solution makes it of wide applicability in a variety of areas, including network design, routing, communication and clustering. In this talk, I will consider the variant under the additional restriction that all degrees of the spanning tree must be at most a given value $k$. The main result I will describe is that one can efficiently find a spanning tree of maximum degree at most $k+2$ whose cost is at most the cost of the optimum spanning tree of maximum degree $k$. This is almost best possible, as the problem of just deciding whether a graph has a spanning tree of maximum degree $k$ is NP-complete.