An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
From MaRDI portal
Publication:4337655
DOI10.1137/S0097539794270881zbMath0870.05066OpenAlexW1988738304MaRDI 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
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Proximity Search for Maximal Subgraph Enumeration, Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs, Constant Time Enumeration by Amortization, On enumerating all minimal solutions of feedback problems, ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS, Constant amortized time enumeration of Eulerian trails, Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods, Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms, Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs, A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization, Unnamed Item, An algorithm to generate all spanning trees with flow, A pivot Gray code listing for the spanning trees of the fan graph, Exact algorithms for the bottleneck Steiner tree problem, Fast enumeration algorithms for non-crossing geometric graphs, Efficient enumeration of dominating sets for sparse graphs, On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay, Unnamed Item, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Generating 3-vertex connected spanning subgraphs, Listing minimal edge-covers of intersecting families with applications to connectivity problems, The problem of the optimal biobjective spanning tree, Edge-swapping algorithms for the minimum fundamental cycle basis problem, Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices, Divide-and-conquer based all spanning tree generation algorithm of a simple connected graph, Algorithms for generating convex sets in acyclic digraphs
