Degree-constrained spanning tree: Difference between revisions

Revision as of 23:30, 1 November 2005

Revision as of 08:12, 27 November 2005

Line 1:

{{expand}}

In [[graph theory]], a '''degree-constrained spanning tree''' is a [[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:

Degree Constrained Spanning Tree

Input: ''n''-node undirected graph G(V,E); positive integer ''k<='' &le; ''n''.

Question: Does G have a spanning tree in which no node has degree greater than ''k''?

This problem is [[NP-Complete]]. This can be shown by a reduction from the [[Hamiltonian path problem]]. ofIt findingremains NP-complete even if ''k'' is fixed to a Hamiltonianvalue path&ge; 2.

[[Category:Spanning tree]]

== References ==

This problem is NP-Complete. This can be shown by a reduction from the problem of finding a Hamiltonian path.

* {{Book reference|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 0716710455}} A2.1: ND1, pg.206.

[[Category:Spanning tree]]