Difference between revisions of "Strongly Connected Components"

From Algorithm Wiki
Jump to navigation Jump to search
Line 27: Line 27:
|-
|-
| rowspan="1" | Quadratic
| rowspan="1" | Quadratic
|
| [https://link.springer.com/article/10.1007%2FBF01940892 Paul Purdom; 1970 (1970)]
 
[http://www.cs.ox.ac.uk/people/gavin.lowe/parallelDFS.html  Lowe’s Algorithm (2014)]
 
[https://ieeexplore.ieee.org/document/5232029 Renault’s Algorithm (2009)]
 
[https://ieeexplore.ieee.org/document/8133154 OBF Algorithm (2011)]
 
[https://research.vu.nl/en/publications/on-distributed-verification-and-verified-distribution CH Algorithm (2004)]
 
[https://stanford-ppl.github.io/website/papers/sc13-hong.pdf Hong’s algorithm (2013)]
|
|
|-
|-
| rowspan="1" | nlogn
| rowspan="1" | nlogn
|
| [https://www.sciencedirect.com/science/article/pii/0020019071900068 Munro’s algorithm (1971)]
|
|
|-
|-
| rowspan="1" | Linear
| rowspan="1" | Linear
|
| [https://www.sciencedirect.com/science/article/pii/0898122181900080 Kosaraju's algorithm (1978)]
 
[https://www.semanticscholar.org/paper/Depth-First-Search-and-Linear-Graph-Algorithms-Tarjan/385742fffcf113656f0d3cf6c06ef95cb8439dc6 Tarjan's strongly connected components algorithm (1972)]
 
[https://www.worldcat.org/title/discipline-of-programming/oclc/1958445 Path-based strong components algorithm; Dikjstra (1976)]
 
[https://www.sciencedirect.com/science/article/pii/S0020019015001532 Pearce; 2016 (2016)]
 
[https://www.sciencedirect.com/science/article/pii/S002001900000051X?via%3Dihub Path-based depth-first search Gabow (2000)]
 
[https://link.springer.com/chapter/10.1007/3-540-48119-2_16 Couvreur; 1999 (1999)]
|
|
|-
|-

Revision as of 13:25, 15 September 2021

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