A space-efficient algorithm for finding strongly connected components

DOI10.1016/J.IPL.2015.08.010MaRDI QIDQ888958zbMATH OpenOpenAlexDBLPWikidataFDO

Authors David 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

depth-first searchgraph algorithmsstrongly connected components

Mathematics Subject Classification ID

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

Recommendations

• On finding the strongly connected components in a directed graph
• I/O- and CPU-optimal recognition of strongly connected components
• scientific article; zbMATH DE number 5879017
• Space-efficient basic graph algorithms
• RECOGNITION OF STRONGLY CONNECTED COMPONENTS BY THE LOCATION OF NONZERO ELEMENTS OCCURRING IN C(G) = (D - A(G))^-1

Cites work

• An efficient algorithm for computing bisimulation equivalence
• Automated Technology for Verification and Analysis
• Depth-First Search and Linear Graph Algorithms
• Finding dominators revisited (extended abstract)
• On finding the strongly connected components in a directed graph
• Path-based depth-first search for strong and biconnected components
• Three SCC-based emptiness checks for generalized Büchi automata
• Tools and Algorithms for the Construction and Analysis of Systems

Cited in

(7)

• Finding strong components using depth-first search
• Comparative study and proof of single-pass connected components algorithms
• RECOGNITION OF STRONGLY CONNECTED COMPONENTS BY THE LOCATION OF NONZERO ELEMENTS OCCURRING IN C(G) = (D - A(G))^-1
• I/O- and CPU-optimal recognition of strongly connected components
• Path-based depth-first search for strong and biconnected components
• A heuristic approach for dividing graphs into bi-connected components with a size constraint
• Finding strongly connected components of simple digraphs based on granulation strategy

Describes a project that uses

Uses Software

• SciPy
• SPIN

This page was built for publication: A space-efficient algorithm for finding strongly connected components

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q888958)