Search code examples
algorithmgraphminimum-spanning-tree

Stuck on solving the Minimal Spanning Tree problem

I have reduced my problem to finding the minimal spanning tree in the graph. But I want to have one more constraint which is that the total degree for each vertex shouldnt exceed a certain constant factor. How do I model my problem? Is MST the wrong path? Do you know any algorithms that will help me?

One more problem: My graph has duplicate edge weights so is there a way to count the number of unique MSTs? Are there algorithms that do this?

Thank You.

Edit: By degree, I mean the total number of edges connecting the vertex. By duplicate edge weight I mean that two edges have the same weight.

Solution

  • This paper shows how to find, in polynomial time, a spanning tree of maximum degree d + 1 that is at least as good as any spanning tree of maximum degree d: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

    //Edit The original link is currently inactive, try http://research.microsoft.com/pubs/80193/mbdst.pdf instead.