On finding the strongly connected components in a directed graph

DOI10.1016/0020-0190(94)90047-7zbMath0787.68082OpenAlexW2084063516WikidataQ57310094 ScholiaQ57310094MaRDI QIDQ1313703

Esko Nuutila, Eljas Soisalon-Soininen

Publication date: 24 February 1994

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

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90047-7

zbMATH Keywords

transitive closureTarjan's algorithmstrongly connected components

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Diagnosability of delay-deadline failures in fair real time discrete event models, An efficient transitive closure algorithm for cyclic digraphs, Abstraction based verification of stability of polyhedral switched systems, A space-efficient algorithm for finding strongly connected components, Shortest paths with exclusive-disjunction arc pairs conflicts, Layerings of logic programs -- layer decomposable semantics and incremental model computation, A linear programming approach to weak reversibility and linear conjugacy of chemical reaction networks, A decomposition approach for commodity pickup and delivery with time-windows under uncertainty, Fairness of transitions in diagnosability of discrete event systems, Optimizing Pointer Analysis Using Bisimilarity, More efficient on-the-fly LTL verification with Tarjan's algorithm

Cites Work

• Unnamed Item
• A strong-connectivity algorithm and its applications in data flow analysis
• I/O- and CPU-optimal recognition of strongly connected components
• On computing the transitive closure of a relation
• An improved transitive closure algorithm
• Depth-First Search and Linear Graph Algorithms