Minimum degree spanning tree

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

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

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.^[2]

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.^[3]

References

^ ^a ^b Krishnan, Radha; Raghavachari, Balaji (2001). "The Directed Minimum-Degree Spanning Tree Problem". FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 2245. pp. 232–243. doi:10.1007/3-540-45294-X_20. ISBN 978-3-540-43002-5.
^ Haque, Mohammed Atiqul; Uddin, Md. Reaz; Kashem, Md. Abul (2007). "An Algorithm for Finding Minimum Degree Spanning Tree of Series-Parallel Graphs". 2007 International Conference on Information and Communication Technology. pp. 27–31. doi:10.1109/ICICT.2007.375336. ISBN 978-984-32-3394-3. S2CID 17947444.
^ Yao, Guohui; Zhu, Daming; Li, Hengwu; Ma, Shaohan (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. 308 (17): 3951–3959. doi:10.1016/j.disc.2007.07.105.

[kr-1] Krishnan, Radha; Raghavachari, Balaji (2001). "The Directed Minimum-Degree Spanning Tree Problem". FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 2245. pp. 232–243. doi:10.1007/3-540-45294-X_20. ISBN 978-3-540-43002-5.

[2] Haque, Mohammed Atiqul; Uddin, Md. Reaz; Kashem, Md. Abul (2007). "An Algorithm for Finding Minimum Degree Spanning Tree of Series-Parallel Graphs". 2007 International Conference on Information and Communication Technology. pp. 27–31. doi:10.1109/ICICT.2007.375336. ISBN 978-984-32-3394-3. S2CID 17947444.

[3] Yao, Guohui; Zhu, Daming; Li, Hengwu; Ma, Shaohan (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. 308 (17): 3951–3959. doi:10.1016/j.disc.2007.07.105.

[1]

[2]

[3]