Minimum degree spanning tree

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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]