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 spanning 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.
Keywords Graph Theory - Spanning Tree - Enumeration Algorithm