Stuck on solving the Minimal Spanning Tree problem

Question

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.

Answer 1

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.

Answer 2

Garey Johnson had this problem reduce to hamilton :( So this one helped. Approximating the first one: http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt However, better working models are appreciated...

Counting: http://mathworld.wolfram.com/SpanningTree.html . According to this, mathematica has a function. Any suggestions in this one?

Answer 3

Well, it's easy to prove that there may not be a solution: just make your input graph a tree that has a vertex with degree higher than your limit..