Hispanopedia Wiki
Articulo de referencia

Degree-constrained spanning tree

A spanning tree can be constructed where the vertex with the highest degree is 3 (thus, a max degree 3 tree). In graph theory , a degree-constrained spanning tree is a spanning ...

Hispanopedia WikiContenido en espanolLectura gratuita
A spanning tree can be constructed where the vertex with the highest degree is 3 (thus, a max degree 3 tree).

In graph theory, a degree-constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constantk. The degree-constrained spanning tree problem is to determine whether a particular graph has such a spanning tree for a particular k.

Formal definition

Input: n-node undirected graph G(V,E); positive integerk < n.

Question: Does G have a spanning tree in which no node has degree greater than k?

NP-completeness

This problem is NP-complete(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

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.[1]

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

Approximation Algorithm

Fürer & Raghavachari (1994) give an iterative polynomial time algorithm which, given a graph G{\displaystyle G}, returns a spanning tree with maximum degree no larger than Δ∗+1{\displaystyle \Delta ^{*}+1}, where Δ∗{\displaystyle \Delta ^{*}} is the minimum possible maximum degree over all spanning trees. Thus, if k=Δ∗{\displaystyle k=\Delta ^{*}}, such an algorithm will either return a spanning tree of maximum degree k{\displaystyle k} or k+1{\displaystyle k+1}.

Known cases

For the complete bipartite graphKm,n{\displaystyle K_{m,n}} where m≤n{\displaystyle m\leq n}:

Δ∗(Km,n)=1+⌈n−1m⌉{\displaystyle \Delta ^{*}(K_{m,n})=1+\left\lceil {\frac {n-1}{m}}\right\rceil }

References

  1. ↑Bui, T. N. and Zrncic, C. M. 2006. 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.
  • Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5. A2.1: ND1, p. 206.{{citation}}: CS1 maint: postscript (link)
  • Fürer, Martin; Raghavachari, Balaji (1994), "Approximating the minimum-degree Steiner tree to within one of optimal", Journal of Algorithms, 17 (3): 409–423, CiteSeerX 10.1.1.136.1089, doi:10.1006/jagm.1994.1042.