ali.mashreghi's blog

Minimum Spanning Tree with lower bound on the degree of non-leaf nodes
By ali.mashreghi, 11 years ago, In English

Hello every one, I wonder if there is an exact or approximation algorithm for the following problem: given a complete weighted graph, find a a minimum spanning tree such that the degree of each non-leaf node is bigger than a constant number (say b).

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Hm, it would be nice Challenge problem for CodeChef if solution is not found :)

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

ha, found it! the name of the problem is "min-degree bounded minimum spanning tree" and has been proved to be NP-hard, there are a few papers which have tried to solve it using an operational research approach.

→ Reply