An algorithm for the enumeration of spanning trees (Q1082082)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An algorithm for the enumeration of spanning trees |
scientific article |
Statements
An algorithm for the enumeration of spanning trees (English)
0 references
1986
0 references
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.
0 references
spanning trees of an undirected graph
0 references
enumeration algorithm
0 references
contractions
0 references
time complexity
0 references
space complexity
0 references