Revision as of 19:00, 17 June 2009 edit Mohitsinghr (talk \| contribs) 13 edits No edit summary ← Previous edit		Revision as of 19:00, 17 June 2009 edit undo Mohitsinghr (talk \| contribs) 13 edits No edit summary Next edit →
Line 11: This problem is [[NP-complete]]. This can be shown by a reduction from the [[Hamiltonian path problem]]. It remains NP-complete even if ''k'' is fixed to a value ≥ 2. If the problem is defined as the degree must be ≤ ''k'', the ''k'' = 2 case of degree-confined spanning tree is the Hamiltonian path problem. ==Approximation ~~Algorithms~~Algorithm== Furer and Raghavachari gave an approximation algorithm for the problem which either shows that there is no tree of maximum degree k or returns a tree of maximum degree k+1.

Degree-constrained spanning tree: Difference between revisions