Jump to content

Degree-constrained spanning tree

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Dcoetzee (talk | contribs) at 08:12, 27 November 2005 (Add reference, links, details, fmt). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.


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:

Input: n-node undirected graph G(V,E); positive integer k ≤ 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. It remains NP-complete even if k is fixed to a value ≥ 2.

References

  • . ISBN 0716710455. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help) A2.1: ND1, pg.206.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Degree-constrained_spanning_tree&oldid=29362274"