Degree-constrained spanning tree: Difference between revisions

Revision as of 08:51, 25 September 2006

Revision as of 03:28, 21 December 2006

Line 1:

{{expand}}

{{cleanup-date|December 2006}}

{{wikify}}

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 16 ⟶ 18:

[[Category:Spanning tree]]

[[Category:NP-complete problems]]