Difference between revisions of "Strongly Connected Components"

From Algorithm Wiki
Jump to navigation Jump to search
Line 8: Line 8:


== Step Chart ==
== Step Chart ==
[[File:Strongly_Connected
[[File:Strongly_Connected_ComponentsStepChart.png|350px]]
ComponentsStepChart.png|350px]]


== Improvement Table ==
== Improvement Table ==

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

Strongly Connected ComponentsBoundsChart.png

Step Chart

Strongly Connected ComponentsStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic
nlogn
Linear
logn