Degree-constrained spanning tree: Difference between revisions

Revision as of 17:28, 13 January 2009

Revision as of 18:59, 17 June 2009

Line 1:

In [[graph theory]], a '''degree-constrained spanning tree''' is a [[spanning tree (mathematics)|spanning tree]] where the maximum [[Degree (graph theory)|vertex degree]] is limited to a certain [[constant]] ''k''. The '''degree-constrained spanning tree problem''' is to determine whether a particular [[Graph (mathematics)|graph]] has such a spanning tree for a particular ''k''.

Line 11 ⟶ 10:

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

Furer and Raghavachari give 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. It is one of the

==References==