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

Q: By vertex degrees do you mean degree between the link incoming into the node and the outgoing link from the node? A: if this is the case you add a condition such as that:

if angle(link1, link2) <> certain_value_Degrees
then (find next path using MST)
else (discard path link1, link2 and looking for a new one -or-)

Q: By Duplicate edge weights, does that mean that a link will have a weight A for condition A and weight b for condition b? A: If this is the case you can deal with it by assigning two links A, B with different weights, or you can do it as a maximum flow problem

Answer 2

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..

Answer 3

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 4

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.