An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs

DOI10.1137/S0097539794270881zbMath0870.05066MaRDI QIDQ4337655

Akiyoshi Shioura, Akihisa Tamura, Takeaki Uno

Publication date: 26 May 1997

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

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, Fast enumeration algorithms for non-crossing geometric graphs, 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, The problem of the optimal biobjective spanning tree, 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