On finding the strongly connected components in a directed graph

DOI10.1016/0020-0190(94)90047-7MaRDI QIDQ1313703zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

strongly connected componentsTarjan's algorithmtransitive closure

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5879017
• I/O- and CPU-optimal recognition of strongly connected components
• A simplified correctness proof for a well-known algorithm computing strongly connected components.
• scientific article; zbMATH DE number 2079387
• An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs

Cites work

• A strong-connectivity algorithm and its applications in data flow analysis
• An improved transitive closure algorithm
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3481857 (Why is no real title available?)
• I/O- and CPU-optimal recognition of strongly connected components
• On computing the transitive closure of a relation

Cited in

(27)

• Determining uni-connectivity in directed graphs
• An efficient transitive closure algorithm for cyclic digraphs
• A semi-automatic proof of strong connectivity
• A simplified correctness proof for a well-known algorithm computing strongly connected components.
• An analysis of repeated graph search
• Abstraction based verification of stability of polyhedral switched systems
• Finding strongly connected components of simple digraphs based on granulation strategy
• An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
• More efficient on-the-fly LTL verification with Tarjan's algorithm
• On computing the 2-vertex-connected components of directed graphs
• Path-based depth-first search for strong and biconnected components
• Diagnosability of delay-deadline failures in fair real time discrete event models
• An Improved Strong Connectivity Discriminant Algorithm for Complex Directed Networks
• Optimizing Pointer Analysis Using Bisimilarity
• Twinless strongly connected components
• Formal methods of paralleling the Tarjan algorithm
• A linear programming approach to weak reversibility and linear conjugacy of chemical reaction networks
• RECOGNITION OF STRONGLY CONNECTED COMPONENTS BY THE LOCATION OF NONZERO ELEMENTS OCCURRING IN C(G) = (D - A(G))^-1
• scientific article; zbMATH DE number 2079387 (Why is no real title available?)
• A decomposition approach for commodity pickup and delivery with time-windows under uncertainty
• On the complexity of strongly connected components in directed hypergraphs
• Shortest paths with exclusive-disjunction arc pairs conflicts
• Layerings of logic programs -- layer decomposable semantics and incremental model computation
• Fast and precise handling of positive weight cycles for field-sensitive pointer analysis
• Finding strong components using depth-first search
• Fairness of transitions in diagnosability of discrete event systems
• A space-efficient algorithm for finding strongly connected components

This page was built for publication: On finding the strongly connected components in a directed graph

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