ISSN:
1572-9125
Keywords:
Graph Theory
;
Spanning Tree
;
Enumeration Algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract 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 isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n 2). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01939361
Permalink
