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 128.174.251.29 (talk) at 23:30, 1 November 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.


Degree Constrained Spanning Tree

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 problem of finding a Hamiltonian path.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Degree-constrained_spanning_tree&oldid=27114500"