Strongly Connected Components

From Algorithm Wiki
Jump to navigation Jump to search

Problem Description

The strongly connected components or diconnected components of an arbitrary

directed graph form a partition into subgraphs that are themselves
strongly connected.

Bounds Chart

Strongly Connected ComponentsBoundsChart.png

Step Chart

Strongly Connected ComponentsStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic Paul Purdom; 1970 (1970)

Lowe’s Algorithm (2014)

Renault’s Algorithm (2009)

OBF Algorithm (2011)

CH Algorithm (2004)

Hong’s algorithm (2013)

nlogn Munro’s algorithm (1971)
Linear Kosaraju's algorithm (1978)

Tarjan's strongly connected components algorithm (1972)

Path-based strong components algorithm; Dikjstra (1976)

Pearce; 2016 (2016)

Path-based depth-first search Gabow (2000)

Couvreur; 1999 (1999)

logn