Portal de Periódicos da CAPES

On finding the strongly connected components in a directed graph

1994; Elsevier BV; Volume: 49; Issue: 1 Linguagem: Inglês

10.1016/0020-0190(94)90047-7

1872-6119

Esko Nuutila, Eljas Soisalon-Soininen,

Graph Labeling and Dimension Problems

We present two improved versions of Tarjan's algorithm for the detection of strongly connected components in a directed graph. Our new algorithms handle sparse graphs and graphs with many trivial components (containing only one node) more economically than Tarjan's original algorithm. As an application we present an efficient transitive closure algorithm.