Skip to main content


Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.10.2019 | Survey and State of the Art | Ausgabe 3/2019 Open Access

Complex & Intelligent Systems 3/2019

Algorithms for generating all possible spanning trees of a simple undirected connected graph: an extensive review

Complex & Intelligent Systems > Ausgabe 3/2019
Maumita Chakraborty, Sumon Chowdhury, Joymallya Chakraborty, Ranjan Mehera, Rajat Kumar Pal
Wichtige Hinweise

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


Generation of all possible spanning trees of a graph is a major area of research in graph theory as the number of spanning trees of a graph increases exponentially with graph size. Several algorithms of varying efficiency have been developed since early 1960s by researchers around the globe. This article is an exhaustive literature survey on these algorithms, assuming the input to be a simple undirected connected graph of finite order, and contains detailed analysis and comparisons in both theoretical and experimental behavior of these algorithms.
Über diesen Artikel

Weitere Artikel der Ausgabe 3/2019

Complex & Intelligent Systems 3/2019 Zur Ausgabe

Premium Partner