An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs

DOI10.1137/S0097539794270881zbMath0870.05066MaRDI QIDQ4337655

Takeaki Uno, Akiyoshi Shioura, Akihisa Tamura

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

optimal algorithm; undirected graphs; spanning trees

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS, Unnamed Item, Unnamed Item, Proximity Search for Maximal Subgraph Enumeration, Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices, Fast enumeration algorithms for non-crossing geometric graphs, Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms, A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization, Exact algorithms for the bottleneck Steiner tree problem, Generating 3-vertex connected spanning subgraphs, Listing minimal edge-covers of intersecting families with applications to connectivity problems, Edge-swapping algorithms for the minimum fundamental cycle basis problem, Algorithms for generating convex sets in acyclic digraphs, On enumerating all minimal solutions of feedback problems, An algorithm to generate all spanning trees with flow, Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods, The problem of the optimal biobjective spanning tree, Efficient enumeration of dominating sets for sparse graphs, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Divide-and-conquer based all spanning tree generation algorithm of a simple connected graph, Constant amortized time enumeration of Eulerian trails, Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs, A pivot Gray code listing for the spanning trees of the fan graph, Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs, Constant Time Enumeration by Amortization, On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay