Depth-First Search and Linear Graph Algorithms
From MaRDI portal
Publication:5663889
DOI10.1137/0201010zbMath0251.05107WikidataQ55952575 ScholiaQ55952575MaRDI QIDQ5663889
Publication date: 1972
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/385742fffcf113656f0d3cf6c06ef95cb8439dc6
05C35: Extremal problems in graph theory
90B40: Search theory
05C20: Directed graphs (digraphs), tournaments
05-04: Software, source code, etc. for problems pertaining to combinatorics
Related Items
Unnamed Item, On Eigenproblem for Circulant Matrices in Max-Algebra, Some theoretical properties of Feng-Schnabel algorithm for block bordered nonlinear systems, Optimum feedback patterns in multivariable control systems, Search for a unique incidence matrix of a graph, Bijective comparison of optimal planarity algorithms, Shortcutting Planar Digraphs, Computing the Rabin Index of a Parity Automaton, INVESTIGATION OF DYNAMICAL SYSTEMS USING SYMBOLIC IMAGES: EFFICIENT IMPLEMENTATION AND APPLICATIONS, All Circuits Enumeration in Macro-Econometric Models, Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Airspace sectorization with constraints, AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY, On the graph traversal method for evaluating linear binary-chain programs, A fully dynamic algorithm for maintaining the transitive closure, MAXIMUM INDEPENDENT, MINIMALLY REDUNDANT SETS IN SERIES-PARALLEL GRAPHS, On the impact of stratification on the complexity of nonmonotonic reasoning, Computing congruence lattices of finite lattices, Control and simulation of hybrid systems, An improved transitive closure algorithm, A linear algorithm for the number of degree constrained subforests of a tree, An improved algorithm for hierarchical clustering using strong components, Graph-theoretical approach to qualitative solvability of linear systems, The monadic second-order logic of graphs. VIII: Orientations, A note on finding the bridges of a graph, A linear time algorithm for the bottleneck biconnected spanning subgraph problem, A transformation which preserves the clique number, A simplified correctness proof for a well-known algorithm computing strongly connected components., An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree, A distributed ant algorithm for efficiently patrolling a network, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, An efficient algorithm for computing bisimulation equivalence, MudPie: layers in the ball of mud, Fully dynamic biconnectivity in graphs, A linear algorithm to decompose inheritance graphs into modules, Unique satisfiability of Horn sets can be solved in nearly linear time, Extremal eigenproblem for bivalent matrices, A capacitated general routing problem on mixed networks, An optimal parallel algorithm for planar cycle separators, Toughness, hamiltonicity and split graphs, Algorithms for dense graphs and networks on the random access computer, Matrix scaling for large-scale system decomposition, Decomposition of a bidirected graph into strongly connected components and its signed poset structure, Propositional semantics for disjunctive logic programs, On some properties of DNA graphs, Naturally submodular digraphs and forbidden digraph configurations, Drawing a tree on parallel lines, Balancing sparse matrices for computing eigenvalues, Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order, An algorithm for obtaining the chromatic number and an optimal coloring of a graph, A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G, The Boolean pivot operation, \(M\)-matrices, and reducible matrices, On the core of information graph games, Balancing sparse Hamiltonian eigenproblems, Fast computation of multiphase flow in porous media by implicit discontinuous Galerkin schemes with optimal ordering of elements, Simple priorities and core stability in hedonic games, Modeling country risk ratings using partial orders, Map construction of unknown graphs by multiple agents, An incremental algorithm for generating all minimal models, The source location problem with local 3-vertex-connectivity requirements, Symbolic graphs: Linear solutions to connectivity related problems, Efficient algorithms for deciding the type of growth of products of integer matrices, Quantitative methods for ecological network analysis, An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps, On global warming: Flow-based soft global constraints, Augmenting forests to meet odd diameter requirements, Table design in dynamic programming, Steiner centers and Steiner medians of graphs, More efficient on-the-fly LTL verification with Tarjan's algorithm, Maximally permissive mutually and globally nonblocking supervision with application to switching control, Communication in m-connected graphs, Cascading flowlines and layout modules: Practical strategies for machine duplication in facility layouts, Multigraph augmentation under biconnectivity and general edge-connectivity requirements, A polynomial algorithm for the max-cut problem on graphs without long odd cycles, Parallel breadth-first search algorithms for trees and graphs, DECOMPOSITION OF GEOMETRIC CONSTRAINT SYSTEMS: A SURVEY, Sparsity in convex quadratic programming with interior point methods, UN-KLEENE BOOLEAN EQUATION SOLVING, Linear time algorithms for finding sparsest cuts in various graph classes, Parameterized Algorithms and Hardness Results for Some Graph Motif Problems, DESIGN AND SYNTHESIS OF SYNCHRONIZATION SKELETONS USING BRANCHING TIME TEMPORAL LOGIC, When Is Reachability Intrinsically Decidable?, Genetic Programming and Model Checking: Synthesizing New Mutual Exclusion Algorithms, Minimizing Coordination Channels in Distributed Testing, From Monomorphic to Polymorphic Well-Typings and Beyond, Unnamed Item, Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs, Finding triconnected components of graphs, Generating Nonisomorphic Maps without Storing Them, A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities, Sensitivity analysis of linear systems—a structural approach, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, A POINT BASIS FOR MULTIVARIABLE PIECEWISE LINEAR INTERPOLATION AND DESIGN CENTERING, Local optimization of colorings of graphs, Unnamed Item, An 0(log n) parallel algorithm for strong connectivity augmentation problem, An algorithm for finding all thek-components of a digraph, On modelling and differential/algebraic systems, Reducing the number of adjustments required in an effector, Analysis of program structure, Optimum matching forests I: Special weights, On Nonnegative matrices generating a finite multiplicative monoid, Searching forK3,3in linear time, Pole assignment problem: a structural investigation, Design of an atomized organization structure: a graph-theoretic approach, Applications of graph theory in computer systems, A search strategy for the elementary cycles of a directed graph, An algorithm for the determination of longest distances in a graph, Reduktion von Präzedenzstrukturen, A note on the decomposition of systems of sparse non-linear equations, On reachability of dynamic systems†, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, On pure structure of dynamic systems, A new algorithm for digraph isomorphism, A polynomial-time algorithm for optimal clustering in a special class of {0, l} -matrices, Parallel \(\mathcal H\)-matrix arithmetics on shared memory systems, A linear algorithm for the cutting center of a tree, Recognizing sign solvable graphs, Domino tilings and related models: Space of configurations of domains with holes, A weight-balanced branching rule for SAT, Using multiset discrimination to solve language processing problems without hashing, Unique Horn renaming and Unique 2-Satisfiability, Element perturbation problems of optimum spanning trees with two-parameter objectives, An algorithm for finding homogeneous pairs, Downwind numbering: Robust multigrid for convection-diffusion problems, On depth first search trees in \(m\)-out digraphs, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, Monge and feasibility sequences in general flow problems, Computational complexity to verify the unstability of effectivity function, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, Go with the winners: a general Monte Carlo strategy, Maximizing sharing of protected information, Reducing the time complexity of testing for local threshold testability, Traversing graphs in a paging environment, BFS or DFS?, A perfect matching algorithm for sparse bipartite graphs, A linear-time algorithm for classifying the states of a finite Markov chain, Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones, A parallel search algorithm for directed acyclic graphs, Classes of matrices for the traveling salesman problem, A taxonomy of fairness and temporal logic problems for Petri nets, Improved algorithms for graph four-connectivity, Chain packing in graphs, Efficient polynomial algorithms for distributive lattices, ASSAT: computing answer sets of a logic program by SAT solvers, Checking timed Büchi automata emptiness efficiently, An efficient bounds consistency algorithm for the global cardinality constraint, Safe separators for treewidth, Solving shortest paths efficiently on nearly acyclic directed graphs, An automata-theoretic approach to the word problem for \(\omega\)-terms over R, Counting solutions to binomial complete intersections, On the reduction of Yutsis graphs, Partitioning multi-edge graphs, A note on locating a central vertex of a 3-cactus graph, A universal table model for categorical databases, The upper envelope of piecewise linear functions: Algorithms and applications, Generalizing the Paige-Tarjan algorithm by abstract interpretation, Graph connectivity, partial words, and a theorem of Fine and Wilf, Feedback vertex set on AT-free graphs, Monotonicity in digraph search problems, Polarity of chordal graphs, Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem, On split-coloring problems, Finding a feasible flow in a strongly connected network, HyPAM: A hybrid continuum-particle model for incompressible free-surface flows, Sur la classification syntaxique, Orientations with single source and sink, Application of net subgroups to the theory of sparse matrices, An algorithm for identifying Morishima and anti-Morishima matrices and balanced digraphs, Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra, An efficient ELL(1)-parser generator, Decomposition by clique separators, Depth-first search is inherently sequential, An approach to the subgraph homeomorphism problem, Sensitivity analysis of an agricultural linear programming model, Solving NP-hard problems in 'almost trees': vertex cover, Uniquely solvable quadratic Boolean equations, A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound, Generalized Steiner problem in outerplanar networks, An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs, System structure: stability and controllability, A compact labelling scheme for series-parallel graphs, A polynomial algorithm for testing the nonnegativity of principal minors of Z-matrices, Efficient symbolic analysis of programs, A decomposition algorithm for multi-terminal network flows, A taxonomy of binary tree traversals, Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery, An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems, On the detection of unstructuredness in flowgraphs, An introduction to the regular theory of fairness, A random NC algorithm for depth first search, A topological approach to dynamic graph connectivity, A linear-processor algorithm for depth-first search in planar graphs, A linear algorithm to solve fixed-point equations on transition systems, Acyclic k-connected subgraphs for distributed alternate routing in communications networks, A decomposition method for minimizing quadratic pseudo-Boolean functions, Stratification and knowledge base management, On orientations and shortest paths, Reasoning with minimal models: efficient algorithms and applications, State-variable planning under structural restrictions: algorithms and complexity, Efficient minimization of homogeneous FSMs for fault diagnosis, Graph traversal and top-down evaluation of logic queries, Uniform data encodings, Optimum and suboptimum methods for permuting a matrix into bordered triangular form, The subgraph homeomorphism problem, Depth-first K-trees and critical path analysis, Degree switching operations in networks and large scale systems assignment problems, The node-deletion problem for hereditary properties is NP-complete, On a cycle finding algorithm, The Schorr-Waite marking algorithm revisited, Maximum matchings and trees, A note on odd and even factors of undirected graphs, A sensitive transitive closure algorithm, An effective structured approach to finding optimal partitions of networks, st-ordering the vertices of biconnected graphs, An algorithm for finding optimum path in networks, A graph theoretic approach to switching function minimization, Depth-first search and the vertex cover problem, Enumerating the cycles of a digraph: a new preprocessing strategy, On minimum dominating sets with minimum intersection, A counting algorithm for a cyclic binary query, On the largest strong components in \(m\)-out digraphs, Complexity of the repeaters allocating problem, The synchronization problem in protocol testing and its complexity, DFS-traversing graphs in a paging environment, LRU or MRU!, An additive bounding procedure for the asymmetric travelling salesman problem, Maintaining bridge-connected and biconnected components on-line, A linear-time algorithm for finding an ambitus, A model classifying algorithms as inherently sequential with applications to graph searching, A linear time algorithm for computing 3-edge-connected components in a multigraph, A new fixed point approach for stable networks and stable marriages, Parallel search algorithms for graphs and trees, The multicovering problem, I/O- and CPU-optimal recognition of strongly connected components, Partitioning, tearing and modification of sparse linear systems, A new algorithm for finding weak components, Deriving graphs from graphs by applying a production, On the vector representation of the reachability in planar directed graphs, Edge-disjoint spanning trees and depth-first search, Some properties of a centroid of a free tree, Testing flow graph reducibility, An algorithm for finding the transitive closure of a digraph, On maximally distant spanning trees of a graph, Computational experiences with some transitive closure algorithms, Computing an st-numbering, Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs, On computing the transitive closure of a relation, Further results on the Aanderaa-Rosenberg conjecture, On recognizing graph properties from adjacency matrices, The Min-Max Spanning Tree Problem and some extensions, The DT-polynomial approach to discrete time-varying network flow problems, Algorithms for updating minimal spanning trees, Cycle detection in critical path networks, A characterization of the minimum cycle mean in a digraph, A linear-time algorithm for finding all feedback vertices, Large-scale problem analysis and decomposition theory, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Optimum tearing in large scale systems and minimum feedback cutsets of a digraph, Locating an absolute center on graphs that are almost trees, Shortest path algorithms for nearly acyclic directed graphs, On the disjunctive set problem, On finding a biconnected spanning planar subgraph with applications to the facilities layout problem, Routing trains through railway stations: Complexity issues, OLDTNF-based evaluation method for handling recursive queries in deductive databases, Symbolic manipulation techniques for model simplification in object-oriented modelling of large scale continuous systems, Algorithms for solving nonlinear dynamic decision models, Uncovering generalized-network structure in matrices, Ordering algorithms for irreducible sparse linear systems, The expected number of pairs of connected nodes: Pair-connected reliability, Well-founded semantics and stratification for ordered logic programs, On finding the strongly connected components in a directed graph, Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs, A linear time algorithm for unique Horn satisfiability, Representing polyhedra: Faces are better than vertices, Network flow and 2-satisfiability, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, Finding the closed partition of a planar graph, A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs, Independent trees in graphs, Finding all the perfect matchings in bipartite graphs, A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem, On the orbits of the product of two permutations, Data structures for two-edge connectivity in planar graphs, Recognition of \(q\)-Horn formulae in linear time, On the equivalence of constrained and unconstrained flows, An efficient transitive closure algorithm for cyclic digraphs, Characterization of \((m,1)\)-transitive and \((3,2)\)-transitive semi- complete directed graphs, On bandwidth-2 graphs, On renamable Horn and generalized Horn functions, On perfect \(0,\pm 1\) matrices, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, Magic sets revisited, A design of the minimum cost ring-chain network with dual-homing survivability: A tabu search approach, A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs, Improved shortest path algorithms for nearly acyclic graphs, Model-checking large structured Markov chains., On the minimum local-vertex-connectivity augmentation in graphs, A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time, On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles., Minimization algorithms for sequential transducers, An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs, Coloring graphs with no \(\text{odd-}K_4\), Backtracking tactics in the backtrack method for SAT, Relational depth-first-search with applications, 4-edge-coloring graphs of maximum degree 3 in linear time, Algorithms for transitive closure, A linear-time algorithm for solving the center problem on weighted cactus graphs, An efficient algorithm for solving the homogeneous set sandwich problem, Interval routing in reliability networks, An analogue of Hoffman's circulation conditions for max-balanced flows, Exploiting special structure in a primal-dual path-following algorithm, Short encodings of planar graphs and maps, Sorting, linear time and the satisfiability problem, Solving some combinatorial problems on arrays with one-way dataflow, An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid
