An algorithm for the enumeration of spanning trees

DOI10.1007/BF01939361MaRDI QIDQ1082082zbMATH OpenOpenAlexFDO

Authors Pawel Winter

Publication date 1986

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01939361

zbMATH Keywords

contractionsenumeration algorithmspace complexityspanning trees of an undirected graphtime complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• An algorithm for enumerating all spanning trees of a directed graph
• Enumeration of spanning trees of certain graphs
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• Complexity of computation of a spanning tree enumeration algorithm
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs

Cites work

• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Finding All Spanning Trees of Directed and Undirected Graphs
• Gravitational instability and collapse of charged fluid shells
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)

Cited in

(26)

• An algorithm to generate all spanning trees with flow
• New method for counting the number of spanning trees in a two-tree network
• An algorithm for enumerating all spanning trees of a directed graph
• Divide-and-conquer based all spanning tree generation algorithm of a simple connected graph
• Edge-matching graph contractions and their interlacing properties
• Enumeration of spanning trees of graph: alternative methods
• A pivot Gray code listing for the spanning trees of the fan graph
• Memory-efficient enumeration of constrained spanning trees
• Critical analysis of the spanning tree techniques
• New algorithm for generation of spanning trees
• Counting spanning trees in cographs: an algorithmic approach
• scientific article; zbMATH DE number 6101315 (Why is no real title available?)
• Complexity of computation of a spanning tree enumeration algorithm
• scientific article; zbMATH DE number 56828 (Why is no real title available?)
• scientific article; zbMATH DE number 177570 (Why is no real title available?)
• Counting Minimum Weight Spanning Trees
• scientific article; zbMATH DE number 1780162 (Why is no real title available?)
• Enumeration of spanning trees of certain graphs
• MOD-CHAR: an implementation of Char's spanning tree enumeration algorithm and its complexity analysis
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• Listing subgraphs by Cartesian decomposition
• Faster enumeration of all spanning trees of a directed graph
• scientific article; zbMATH DE number 7771742 (Why is no real title available?)
• An algorithm for enumerating all directed spanning trees in a directed graph
• Pivot Gray codes for the spanning trees of a graph ft. the fan
• Exact algorithms for edge deletion to Cactus

This page was built for publication: An algorithm for the enumeration of spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082082)