An algorithm for the enumeration of spanning trees (Q1082082)

Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm is \(O(n+m+nt)\) where n is the number of vertices, m the number of edges, and t the number of spannig trees in the graph. The worst-case space complexity of the algorithm is \(O(n^ 2)\). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.