Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
From MaRDI portal
Publication:4075503
DOI10.1002/net.1975.5.3.237zbMath0316.05125OpenAlexW2767970464MaRDI QIDQ4075503
Ronald C. Read, Robert Endre Tarjan
Publication date: 1975
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.1975.5.3.237
Related Items
Generating all maximal independent sets on trees in lexicographic order, Dual-bounded generating problems: Weighted transversals of a hypergraph, An algorithm for the enumeration of spanning trees, Heuristic and exact algorithms for the spanning tree detection problem, Memory-efficient enumeration of constrained spanning trees, Faster enumeration of all spanning trees of a directed graph, An efficient algorithm for solving pseudo clique enumeration problem, Recognizing max-flow min-cut path matrices, On generating all maximal independent sets, Mining preserving structures in a graph sequence, Enumerating disjunctions and conjunctions of paths and cuts in reliability theory, Reverse search for enumeration, Linearizable special cases of the quadratic shortest path problem, Efficiently enumerating all spanning trees of a plane 3-tree (extended abstract), On a cycle finding algorithm, Probabilistic and exact frequent subtree mining in graphs beyond forests, Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes, Unnamed Item, Listing all spanning trees in Halin graphs — sequential and Parallel view, Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming, An inequality for polymatroid functions and its applications., Unnamed Item, The negative cycles polyhedron and hardness of checking some polyhedral properties, Enumerating the cycles of a digraph: a new preprocessing strategy, An Efficient Algorithm for Enumerating Pseudo Cliques, Generating cut conjunctions in graphs and related problems, Enumerating models of DNF faster: breaking the dependency on the formula size, A search strategy for the elementary cycles of a directed graph, On enumerating minimal dicuts and strongly connected subgraphs, Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, New algorithm for generation of spanning trees, Monadic second-order model-checking on decomposable matroids, Incremental delay enumeration: space and time, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Generating 3-vertex connected spanning subgraphs, On the shortest path problem with negative cost cycles, Cycle detection in critical path networks, Listing minimal edge-covers of intersecting families with applications to connectivity problems, Characterizations of outerplanar graphs, Concave cost minimization on networks, The problem of the optimal biobjective spanning tree, Efficiently enumerating hitting sets of hypergraphs arising in data profiling, Generating all vertices of a polyhedron is hard, Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction, Analyse und Synthese zuverlässiger Netze, Algorithms for generating convex sets in acyclic digraphs, Identifying the structure of cycling in ecosystems, Signsolvability revisited, Logical analysis of data with decomposable structures., On the succinct representation of graphs, Efficient enumeration of the vertices of polyhedra associated with network LP's, Finding all the negative cycles in a directed graph, A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs
