Degree-constrained spanning tree: Difference between revisions

Revision as of 21:20, 13 January 2007

Revision as of 14:37, 12 April 2007

Line 1:

{{Expand|date=January 2007}}

{{Cleanup|date=December 2006}}

{{Wikify|date=December 2006}}

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

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 (in fact, for ''k''=2, this is the Hamiltonian path problem).

== References ==

* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5}} A2.1: ND1, pg.206.