Difference between revisions of "Strongly Connected Components"
Jump to navigation
Jump to search
Yashsherry (talk  contribs) 
Yashsherry (talk  contribs) 

(One intermediate revision by the same user not shown)  
Line 1:  Line 1:  
== Problem Description==  == Problem Description==  
Connectivity in an undirected graph means that every vertex can reach every other vertex via any path. If the graph is not connected the graph can be broken down into Connected Components.  
Strong Connectivity applies only to directed graphs. A directed graph is strongly connected if there is a directed path from any vertex to every other vertex. This is same as connectivity in an undirected graph, the only difference being strong connectivity applies to directed graphs and there should be directed paths instead of just paths. Similar to connected components, a directed graph can be broken down into Strongly Connected Components.  
== Bounds Chart ==  == Bounds Chart ==  
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)]  
    
   
Latest revision as of 13:40, 15 September 2021
Problem Description
Connectivity in an undirected graph means that every vertex can reach every other vertex via any path. If the graph is not connected the graph can be broken down into Connected Components.
Strong Connectivity applies only to directed graphs. A directed graph is strongly connected if there is a directed path from any vertex to every other vertex. This is same as connectivity in an undirected graph, the only difference being strong connectivity applies to directed graphs and there should be directed paths instead of just paths. Similar to connected components, a directed graph can be broken down into Strongly Connected Components.
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 