An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs

DOI10.1137/S0097539794270881MaRDI QIDQ4337655zbMATH OpenOpenAlexFDO

Authors Akiyoshi Shioura, Akihisa Tamura, Takeaki Uno

Publication date 26 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794270881

zbMATH Keywords

spanning treesundirected graphsoptimal algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
• An algorithm for enumerating all spanning trees of a directed graph
• scientific article; zbMATH DE number 177570
• A flexible algorithm for generating all the spanning trees in undirected graphs

Cited in

(36)

• Constant time enumeration by amortization
• Edge-swapping algorithms for the minimum fundamental cycle basis problem
• An algorithm to generate all spanning trees with flow
• The problem of the optimal biobjective spanning tree
• Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs
• Pivot Gray codes for the spanning trees of a graph ft. the fan
• Listing subgraphs by Cartesian decomposition
• Listing all the minimum spanning trees in an undirected graph
• Generating 3-vertex connected spanning subgraphs
• EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
• Listing minimal edge-covers of intersecting families with applications to connectivity problems
• An algorithm for enumerating all directed spanning trees in a directed graph
• Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
• Computing the Tutte polynomial of a graph of moderate size
• A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
• Algorithms for generating convex sets in acyclic digraphs
• On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay
• ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS
• A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization
• Efficient enumeration of dominating sets for sparse graphs
• Constant amortized time enumeration of Eulerian trails
• Divide-and-conquer based all spanning tree generation algorithm of a simple connected graph
• Efficient enumeration of dominating sets for sparse graphs
• Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods
• Fast enumeration algorithms for non-crossing geometric graphs
• Proximity Search for Maximal Subgraph Enumeration
• On enumerating all minimal solutions of feedback problems
• Exact algorithms for the bottleneck Steiner tree problem
• scientific article; zbMATH DE number 56828 (Why is no real title available?)
• A pivot Gray code listing for the spanning trees of the fan graph
• Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms
• New algorithm for generation of spanning trees
• Output-sensitive listing of bounded-size trees in undirected graphs
• An algorithm for the enumeration of spanning trees
• CAGE: cache-aware graphlet enumeration
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs

This page was built for publication: An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs

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