Difference between revisions of "Strongly Connected Components"
Jump to navigation
Jump to search
Yashsherry (talk | contribs) (Created page with "== Problem Description== The strongly connected components or diconnected components of an arbitrary directed graph form a partition into subgraphs that are themselves stron...") |
Yashsherry (talk | contribs) |
||
| Line 5: | Line 5: | ||
== Bounds Chart == | == Bounds Chart == | ||
[[File: | [[File:Strongly_Connected_ComponentsBoundsChart.png|350px]] | ||
== Step Chart == | == Step Chart == | ||
Revision as of 08:01, 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
[[File:Strongly_Connected ComponentsStepChart.png|350px]]
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | ||
| nlogn | ||
| Linear | ||
| logn |