Depth-First Search and Linear Graph Algorithms
From MaRDI portal
Publication:5663889
DOI10.1137/0201010zbMath0251.05107OpenAlexW2118382442WikidataQ55952575 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
Extremal problems in graph theory (05C35) Search theory (90B40) Directed graphs (digraphs), tournaments (05C20) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items (only showing first 100 items - show all)
On computing the 2-vertex-connected components of directed graphs ⋮ Strong articulation points and strong bridges in large scale graphs ⋮ Polynomial recognition of cluster algebras of finite type ⋮ The incremental maintenance of a depth-first-search tree in directed acyclic graphs ⋮ A linear time algorithm for finding depth-first spanning trees on trapezoid graphs ⋮ Path-based depth-first search for strong and biconnected components ⋮ Diagnosability of Petri nets with observation graphs ⋮ Simple DFS on the complement of a graph and on partially complemented digraphs ⋮ Integer programming formulations for the elementary shortest path problem ⋮ A multiobjective distance separation methodology to determine sector-level minimum separation for safe air traffic scenarios ⋮ Power optimization in ad hoc wireless network topology control with biconnectivity requirements ⋮ A branch-and-bound algorithm for the acyclic partitioning problem ⋮ The min-max split delivery multi-depot vehicle routing problem with minimum service time requirement ⋮ Solving the team orienteering problem with cutting planes ⋮ The solution of the linear complementarity problem by the matrix analogue of the accelerated overrelaxation iterative method ⋮ Revealed preference test and shortest path problem; graph theoretic structure of the rationalizability test ⋮ Synthesis of large dynamic concurrent programs from dynamic specifications ⋮ An extended framework for passive asynchronous testing ⋮ Toward incremental computation of argumentation semantics: a decomposition-based approach ⋮ Domino tilings and related models: Space of configurations of domains with holes ⋮ A weight-balanced branching rule for SAT ⋮ Problems on cycles and colorings ⋮ The balanced traveling salesman problem ⋮ A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars ⋮ Finding dominators via disjoint set union ⋮ Recognition and characterization of chronological interval digraphs ⋮ A general label search to investigate classical graph search algorithms ⋮ Minimal counterexamples for linear-time probabilistic verification ⋮ Efficiently mining \(\delta \)-tolerance closed frequent subgraphs ⋮ Finding all maximally-matchable edges in a bipartite graph ⋮ Reasoning about visibility ⋮ Numerical construction of LISS Lyapunov functions under a small-gain condition ⋮ The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\) ⋮ Sequential and distributed on-the-fly computation of weak tau-confluence ⋮ Self-stabilizing algorithm for high service availability in spite of concurrent topology changes in ad hoc mobile networks ⋮ A post-improvement procedure for the mixed load school bus routing problem ⋮ Scenario based robust line balancing: Computational complexity ⋮ GMPLS label space minimization through hypergraph layouts ⋮ Finding strong bridges and strong articulation points in linear time ⋮ On graphs with no induced subdivision of \(K_4\) ⋮ Weight constraint programs with evaluable functions ⋮ Number of holes in unavoidable sets of partial words. II. ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Efficient total domination in digraphs ⋮ Topological ordering algorithm for LDAG ⋮ Disjunctive closures for knowledge compilation ⋮ The eigenvectors corresponding to the second eigenvalue of the google matrix and their relation to link spamming ⋮ Necessary conditions for the generic global rigidity of frameworks on surfaces ⋮ Maximizing entropy over Markov processes ⋮ Complexity of fuzzy answer set programming under Łukasiewicz semantics ⋮ Growth properties of power-free languages ⋮ An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time lags ⋮ Application of auxiliary space preconditioning in field-scale reservoir simulation ⋮ Topological sorts on DAGs ⋮ Trémaux trees and planarity ⋮ Dulmage-Mendelsohn canonical decomposition as a generic pruning technique ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Space-efficient biconnected components and recognition of outerplanar graphs ⋮ Preprocessing for a map sectorization problem by means of mathematical programming ⋮ A decomposition approach for commodity pickup and delivery with time-windows under uncertainty ⋮ A note on testing axioms of revealed preference ⋮ Computing periodic request functions to speed-up the analysis of non-cyclic task models ⋮ Indeterminate strings, prefix arrays \& undirected graphs ⋮ Using multiset discrimination to solve language processing problems without hashing ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ 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 ⋮ Confluence reduction for Markov automata ⋮ Stability analysis of stochastic coupled systems on networks without strong connectedness via hierarchical approach ⋮ On robust input design for nonlinear dynamical models ⋮ Component-wise incremental LTL model checking ⋮ Computing maximal weak and other bisimulations ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ State space search nogood learning: online refinement of critical-path dead-end detectors in planning ⋮ The geo-graph in practice: creating United States congressional districts from census blocks ⋮ On the complexity of strongly connected components in directed hypergraphs ⋮ On depth first search trees in \(m\)-out digraphs ⋮ Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components ⋮ Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ Three enhancements for optimization-based bound tightening ⋮ Rigorous bounds for polynomial Julia sets ⋮ Strip planarity testing for embedded planar graphs ⋮ A distributed social choice protocol for combinatorial domains ⋮ Block-graph width ⋮ Finite resolution dynamics ⋮ The extended global cardinality constraint: an empirical survey ⋮ Component-based construction of bio-pathway models: the parameter estimation problem ⋮ IDD-based model validation of biochemical networks ⋮ Decision problems for convex languages ⋮ Parallel \(\mathcal H\)-matrix arithmetics on shared memory systems ⋮ A linear algorithm for the cutting center of a tree ⋮ Recognizing sign solvable graphs ⋮ Semi-equilibrium models for paracoherent answer set programs ⋮ Computation of Lyapunov functions for systems with multiple local attractors ⋮ Efficient computation of Lyapunov functions for Morse decompositions ⋮ Parameterized complexity of the anchored \(k\)-core problem for directed graphs ⋮ A fast algorithm to construct a representation for transversal matroids
This page was built for publication: Depth-First Search and Linear Graph Algorithms
