Content deleted Content added
Add reference, links, details, fmt |
m dab |
||
Line 1:
{{expand}}
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:
Input: ''n''-node undirected graph G(V,E); positive integer ''k'' ≤ ''n''.
| |||