Strongly Connected Components

From Algorithm Wiki
Revision as of 08:01, 15 September 2021 by 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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

[[File:Strongly_Connected ComponentsBoundsChart.png|350px]]

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