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/ondistributedverificationandverifieddistribution CH Algorithm (2004)]  
[https://stanfordppl.github.io/website/papers/sc13hong.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/DepthFirstSearchandLinearGraphAlgorithmsTarjan/385742fffcf113656f0d3cf6c06ef95cb8439dc6 Tarjan's strongly connected components algorithm (1972)]  
[https://www.worldcat.org/title/disciplineofprogramming/oclc/1958445 Pathbased 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 Pathbased depthfirst search Gabow (2000)]  
[https://link.springer.com/chapter/10.1007/3540481192_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) Pathbased strong components algorithm; Dikjstra (1976) 

logn 