Strongly Connected Components: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "== 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 ap...")
 
No edit summary
Line 1: Line 1:
== Problem Description==
{{DISPLAYTITLE:Strongly Connected Components (Strongly Connected Components)}}
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.
== Description ==  


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.
The strongly connected components or diconnected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected.


== Bounds Chart ==
== Related Problems ==  
[[File:Strongly_Connected_ComponentsBoundsChart.png|1050px]]


== Step Chart ==
Related: [[Transitive Closure]], [[Maximum Strongly Connected Component]], [[Strong Connectivity (dynamic)]], [[2 Strong Components (dynamic)]], [[Connected Subgraph]]
[[File:Strongly_Connected_ComponentsStepChart.png|1050px]]


== Improvement Table ==
== Parameters ==  
{| class="wikitable" style="text-align:center;" width="100%"
!width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links
|-
| rowspan="1" | Exp/Factorial
|
|
|-
| rowspan="1" | Polynomial > 3
|
|
|-
| rowspan="1" | Cubic
|
|
|-
| 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)]
<pre>V: number of vertices
E: number of edges</pre>


[https://ieeexplore.ieee.org/document/5232029 Renault’s Algorithm (2009)]
== Table of Algorithms ==


[https://ieeexplore.ieee.org/document/8133154 OBF Algorithm (2011)]
Currently no algorithms in our database for the given problem.


[https://research.vu.nl/en/publications/on-distributed-verification-and-verified-distribution CH Algorithm (2004)]
== Time Complexity graph ==


[https://stanford-ppl.github.io/website/papers/sc13-hong.pdf Hong’s algorithm (2013)]
[[File:Strongly Connected Components - Time.png|1000px]]
|
|-
| rowspan="1" | nlogn
| [https://www.sciencedirect.com/science/article/pii/0020019071900068 Munro’s algorithm (1971)]
|
|-
| 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)]
== Space Complexity graph ==


[https://www.worldcat.org/title/discipline-of-programming/oclc/1958445 Path-based strong components algorithm; Dikjstra (1976)]
[[File:Strongly Connected Components - Space.png|1000px]]


[https://www.sciencedirect.com/science/article/pii/S0020019015001532 Pearce; 2016 (2016)]
== Pareto Decades graph ==


[https://www.sciencedirect.com/science/article/pii/S002001900000051X?via%3Dihub Path-based depth-first search Gabow (2000)]
[[File:Strongly Connected Components - Pareto Frontier.png|1000px]]
 
[https://link.springer.com/chapter/10.1007/3-540-48119-2_16 Couvreur; 1999 (1999)]
|
|-
| rowspan="1" | logn
|
|
|-|}

Revision as of 11:19, 15 February 2023

Description

The strongly connected components or diconnected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected.

Related Problems

Related: Transitive Closure, Maximum Strongly Connected Component, Strong Connectivity (dynamic), 2 Strong Components (dynamic), Connected Subgraph

Parameters

V: number of vertices
E: number of edges

Table of Algorithms

Currently no algorithms in our database for the given problem.

Time Complexity graph

Strongly Connected Components - Time.png

Space Complexity graph

Strongly Connected Components - Space.png

Pareto Decades graph

Strongly Connected Components - Pareto Frontier.png

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Strongly_Connected_Components&oldid=43902"