Content deleted Content added
m Fixing links to disambiguation pages, replaced: graph{{dn|date=January 2016}} → graph using AWB |
m Remove blank line(s) between list items per WP:LISTGAP to fix an accessibility issue for users of screen readers. Do WP:GENFIXES and cleanup if needed. Discuss this at Wikipedia talk:WikiProject Accessibility#LISTGAP |
||
Line 1:
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'' ≤ ''n''.
Question: Does G have a spanning tree in which no [[Node (computer science)|node]] has degree greater than ''k''?
Line 24:
{{Reflist}}
* {{citation|author1-link = Michael R. Garey|first1=Michael R.|last1=Garey|author2-link=David S. Johnson|first2=David S.|last2=Johnson | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5|postscript=. A2.1: ND1, p. 206.}}
*{{citation|first1=Martin|last1=Fürer|first2=Balaji|last2=Raghavachari|year=1994|title=Approximating the minimum-degree Steiner tree to within one of optimal|journal=Journal of Algorithms|volume=17|issue=3|pages=409–423|doi=10.1006/jagm.1994.1042|postscript=.}}
| |||