Finding All Spanning Trees of Directed and Undirected Graphs

DOI10.1137/0207024zbMath0379.68031WikidataQ56271082 ScholiaQ56271082MaRDI QIDQ4158476

Harold N. Gabow, Eugene W. Myers

Publication date: 1978

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

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

Mathematics Subject Classification ID

05C05: Trees

05C20: Directed graphs (digraphs), tournaments

68W99: Algorithms in computer science

Related Items

Distributed Consensus for Multiagent Systems via Directed Spanning Tree Based Adaptive Control, Listing all spanning trees in Halin graphs — sequential and Parallel view, Obtaining the long-term behavior of master equations with finite state space from the structure of the associated state transition network, Faster enumeration of all spanning trees of a directed graph, A consensus protocol under directed communications with two time delays and delay scheduling, Parameterized Complexity for Domination Problems on Degenerate Graphs, Efficiently enumerating all spanning trees of a plane 3-tree (extended abstract), Explicit expressions for stationary states of the Lindblad equation for a finite state space, Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms, Resource levelling in project scheduling with generalized precedence relationships and variable execution intensities, Memory-efficient enumeration of constrained spanning trees, Algorithmic parameterization of mixed treatment comparisons, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, 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, Combinatorial analysis (nonnegative matrices, algorithmic problems), An algorithm for the enumeration of spanning trees, An algorithm to generate all spanning trees with flow, Consensus of nonlinear multi-agent systems with directed switching graphs: a directed spanning tree based error system approach, Stabilizability analysis and switching signals design of switched Boolean networks, Enumerating all spanning trees for pairwise comparisons, The problem of the optimal biobjective spanning tree, A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs, Mixed-integer linear programming for resource leveling problems, Divide-and-conquer based all spanning tree generation algorithm of a simple connected graph, Beyond the BEST theorem: fast assessment of Eulerian trails, On the complexity of connectivity in cognitive radio networks through spectrum assignment, Observer-based consensus for multi-agent systems with partial adaptive dynamic protocols, Exact methods for the resource levelling problem, Ninth and tenth order virial coefficients for hard spheres in \(D\) dimensions, A pivot Gray code listing for the spanning trees of the fan graph, Stability of formation control using a consensus protocol under directed communications with two time delays and delay scheduling, On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay