Finding All Spanning Trees of Directed and Undirected Graphs

DOI10.1137/0207024zbMath0379.68031OpenAlexW2022871748WikidataQ56271082 ScholiaQ56271082MaRDI QIDQ4158476

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

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Algorithms in computer science (68W99)

Related Items (37)

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

This page was built for publication: Finding All Spanning Trees of Directed and Undirected Graphs