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

space complexitytime complexitycontractionsenumeration algorithmspanning trees of an undirected graph

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• 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

Cited in

(23)

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

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)