Path-based depth-first search for strong and biconnected components

DOI10.1016/S0020-0190(00)00051-XzbMath1339.68301WikidataQ56673385 ScholiaQ56673385MaRDI QIDQ294748

Harold N. Gabow

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S002001900000051X?np=y

zbMATH Keywords

graph algorithmsdepth-first searchstackbiconnected componentstrongly connected component

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Path-based depth-first search for strong and biconnected components, \(\Delta \)-list vertex coloring in linear time, Computing maximal subsemigroups of a finite semigroup, Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits, Separator-based data reduction for signed graph balancing, A space-efficient algorithm for finding strongly connected components, Verification of programs with exceptions through operator precedence automata, The scaling limit of a critical random directed graph, A simple certifying algorithm for 3-edge-connectivity, Enumeration of idempotents in planar diagram monoids, An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton, Space-efficient biconnected components and recognition of outerplanar graphs, Certifying 3-edge-connectivity, On the complexity of strongly connected components in directed hypergraphs, Computing finite semigroups, A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time, Yet another optimal algorithm for 3-edge-connectivity, Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster, Finding strongly connected components of simple digraphs based on granulation strategy, An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton, Stubborn Sets, Frozen Actions, and Fair Testing, Space efficient linear time algorithms for BFS, DFS and applications, 4-edge-coloring graphs of maximum degree 3 in linear time

Uses Software

• GraphBase

Cites Work

• Path-based depth-first search for strong and biconnected components
• A linear-time algorithm for a special case of disjoint set union
• A strong-connectivity algorithm and its applications in data flow analysis
• Parallel concepts in graph theory
• On the computational power of pushdown automata
• Efficient Planarity Testing
• Efficiency of a Good But Not Linear Set Union Algorithm
• Dividing a Graph into Triconnected Components
• Cycle Length in a Random Function
• Depth-First Search and Linear Graph Algorithms
• Time and tape complexity of pushdown automaton languages
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item