Surf Wiki
Save to docs
general/spanning-tree

From Surf Wiki (app.surf) — the open knowledge base

Minimum degree spanning tree

Graph theory concept

Summary

Graph theory concept

In graph theory, a minimum degree spanning tree is a subset of the edges of a connected graph that connects all the vertices together, without any cycles, and its maximum degree of its vertices as small as possible. That is, it is a spanning tree whose maximum degree is minimal.

The decision problem is: Given a graph G and an integer k, does G have a spanning tree such that no vertex has degree greater than k? This is also known as the degree-constrained spanning tree problem.

Algorithms

Finding the minimum degree spanning tree of an undirected graph is NP-hard. This can be shown by constructing a reduction from the Hamiltonian path problem. For directed graphs, finding the minimum degree spanning tree is also NP-hard.

R. Krishman and B. Raghavachari (2001) have a quasi-polynomial time approximation algorithm to solve the problem for directed graphs.

M. Haque, Md. R. Uddin, and Md. A. Kashem (2007) found a linear time algorithm that can find the minimum degree spanning tree of series-parallel graphs with small degrees.

G. Yao, D. Zhu, H. Li, and S. Ma (2008) found a polynomial time algorithm that can find the minimum degree spanning tree of directed acyclic graphs.

References

References

  1. (2001). "FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science".
  2. (2007). "2007 International Conference on Information and Communication Technology".
  3. (6 September 2008). "A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem". Discrete Mathematics.
Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

spanning-tree
Want to explore this topic further?

Ask Mako anything about Minimum degree spanning tree — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report