Degree-constrained spanning tree: Difference between revisions

Revision as of 00:20, 29 October 2009

Latest revision as of 19:27, 6 February 2025

(18 intermediate revisions by 12 users not shown)

Line 1:

In [[graph theory]], a '''degreeFile:Degree-constrained spanning tree'''.png|thumb|350px|On isthe left, a [[spanning tree (mathematics)|spanningcan tree]]be constructed where the maximumvertex with the highest [[Degree (graph theory)|vertex degree]] is limited2 to(thus, a certainmax [[Constantdegree (mathematics2 tree)|constant]] ''k''.<br The/> '''degree-constrainedOn spanningthe treeright, problem'''the iscentral tovertex determinemust whetherhave adegree particularat [[Graphleast (mathematics)|graph]]5 hasin suchany atree spanning treethis graph, forso a particular2 ''k''.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'' ≤< ''n''.

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 ≥&nbsp;2. If the problem is defined as the degree must be ≤&nbsp;''k'', the ''k'' = 2 case of degree-confined spanning tree is the Hamiltonian path problem.

==Degree-constrained minimum spanning tree==

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 ≥&nbsp;2. If the problem is defined as the degree must be ≤&nbsp;''k'', the ''k'' = 2 case of degree-confined spanning tree is the Hamiltonian path problem.

On a weighted graph, a Degree-constrained minimum spanning tree (DCMST) is a degree-constrained spanning tree in which the sum of its edges has the minimum possible sum. Finding a DCMST is an NP-Hard problem.<ref>Bui, T. N. and Zrncic, C. M. 2006. [http://www.cs.york.ac.uk/rts/docs/GECCO_2006/docs/p11.pdf An ant-based algorithm for finding degree-constrained minimum spanning tree.]

In GECCO ’06: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 11–18, New York, NY, USA. ACM.</ref>

Heuristic algorithms that can solve the problem in polynomial time have been proposed, including Genetic and Ant-Based Algorithms.

==Approximation Algorithm==

{{harvtxt|Fürer|Raghavachari|1994}} gavegive an approximationiterative algorithmpolynomial fortime the problemalgorithm which, ongiven anya givengraph instance<math>G</math>, eitherreturns showsa thatspanning thetree instancewith hasmaximum degree no treelarger ofthan <math>\Delta^* + 1</math>, where <math>\Delta^*</math> is the minimum possible maximum degree over all spanning trees. Thus, if <math>k or= it\Delta^*</math>, findssuch andan returnsalgorithm will either return a spanning tree of maximum degree <math>k</math> or <math>k+1</math>.

==References==

{{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 = 978-0-7167-1045-5|postscript=. A2.1: ND1, p.&nbsp;206.|title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness}}

*{{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=.|citeseerx=10.1.1.136.1089}}

*{{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=.}}

[[Category:Spanning tree]]

[[Category:NP-complete problems]]

{{combin-stub}}