A space-efficient algorithm for finding strongly connected components

DOI10.1016/j.ipl.2015.08.010zbMath1343.68281OpenAlexW1460634171WikidataQ57310095 ScholiaQ57310095MaRDI QIDQ888958

David J. Pearce

Publication date: 5 November 2015

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.08.010

zbMATH Keywords

graph algorithmsdepth-first searchstrongly connected components

Mathematics Subject Classification ID

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

Related Items

A heuristic approach for dividing graphs into bi-connected components with a size constraint

Uses Software

• SPIN
• SciPy

Cites Work

• Path-based depth-first search for strong and biconnected components
• On finding the strongly connected components in a directed graph
• An efficient algorithm for computing bisimulation equivalence
• Three SCC-Based Emptiness Checks for Generalized Büchi Automata
• Tools and Algorithms for the Construction and Analysis of Systems
• Automated Technology for Verification and Analysis
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item