Degree-constrained spanning tree: Difference between revisions

Revision as of 05:59, 14 June 2006

Revision as of 17:22, 28 August 2006

Line 11:

== 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 07167104550-7167-1045-5}} A2.1: ND1, pg.206.

[[Category:Spanning tree]]

If you have defined that the degree must be <= k, the k=2 case of degree-confined spanning tree is the Hamiltonian path problem.

[[Category:Spanning tree]]