Content deleted Content added
Scrabbler94 (talk | contribs) →Approximation Algorithm: original description not quite right, as k is given as input. If k = \Delta^*, where \Delta^* is the minimum max degree over all spanning trees, then it is correct |
→NP-completeness: plnk |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 1:
[[File:Degree-constrained spanning tree.png|thumb|350px|On the left, a spanning tree can be constructed where the vertex with the highest [[Degree (graph theory)|degree]] is 2 (thus, a max degree 2 tree).<br /> On the right, the central vertex must have degree at least 5 in any tree spanning this graph, so a 2 degree constrained tree cannot be constructed here.]]
In [[graph theory]], a '''degree-constrained spanning tree''' is a [[spanning tree (mathematics)|spanning tree]] where the maximum [[Degree (graph theory)|vertex degree]] is limited to a certain [[Constant (mathematics)|constant]] ''k''. The '''degree-constrained spanning tree problem''' is to determine whether a particular [[Graph (discrete mathematics)|graph]] has such a spanning tree for a particular ''k''.
==Formal definition==
Input: ''n''-node undirected graph G(V,E); positive [[integer]] ''k''
Question: Does G have a spanning tree in which no [[Node (computer science)|node]] has degree greater than ''k''?
==NP-completeness==
This problem is [[NP-complete]] {{harv|Garey|Johnson|1979}}. This can be shown by a [[Reduction (complexity)|reduction]] from the [[Hamiltonian path problem]]. It remains NP-complete even if ''k'' is fixed to a value ≥ 2. If the problem is defined as the degree must be ≤ ''k'', the ''k'' = 2 case of degree-confined spanning tree is the Hamiltonian path problem.▼
▲This problem is [[NP-complete]] {{harv|Garey|Johnson|1979}}. 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. If the problem is defined as the degree must be ≤ ''k'', the ''k'' = 2 case of degree-confined spanning tree is the Hamiltonian path problem.
==Degree-constrained minimum spanning tree==
| |||