Minimum degree spanning tree
{{Short description|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 reduction to the Hamiltonian path problem. For directed graphs, finding the minimum degree spanning tree is also NP-hard. {{cite book |last1=Krishnan |first1=Radha |last2=Raghavachari |first2=Balaji |title=FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science |chapter=The Directed Minimum-Degree Spanning Tree Problem |series=Lecture Notes in Computer Science |date=2001 |volume=2245 |pages=232–243 |doi=10.1007/3-540-45294-X_20 |isbn=978-3-540-43002-5 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-45294-X_20}}
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.{{cite book |last1=Haque |first1=Mohammed Atiqul |last2=Uddin |first2=Md. Reaz |last3=Kashem |first3=Md. Abul |title=2007 International Conference on Information and Communication Technology |chapter=An Algorithm for Finding Minimum Degree Spanning Tree of Series-Parallel Graphs |date=2007 |pages=27–31 |doi=10.1109/ICICT.2007.375336 |isbn=978-984-32-3394-3 |s2cid=17947444 |chapter-url=https://ieeexplore.ieee.org/document/4261359}}
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.{{cite journal |last1=Yao |first1=Guohui |last2=Zhu |first2=Daming |last3=Li |first3=Hengwu |last4=Ma |first4=Shaohan |title=A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem |journal=Discrete Mathematics |date=6 September 2008 |volume=308 |issue=17 |pages=3951–3959 |doi=10.1016/j.disc.2007.07.105|doi-access= }}
References
{{reflist}}