Difference between revisions of "Strongly Connected Components"
Jump to navigation
Jump to search
Yashsherry (talk | contribs) |
Yashsherry (talk | contribs) |
||
| 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
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | Paul Purdom; 1970 (1970) | |
| nlogn | Munro’s algorithm (1971) | |
| Linear | Kosaraju's algorithm (1978)
Tarjan's strongly connected components algorithm (1972) Path-based strong components algorithm; Dikjstra (1976) |
|
| logn |