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
    0 references
    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

    Identifiers