Transitive Closure (Strongly Connected Components)

From Algorithm Wiki
Revision as of 09:06, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


In this problem, we also want to compute the transitive closure of a graph. (Perhaps this should be a separate problem?)

Related Problems

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


$V$: number of vertices

$E$: number of edges

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Paul Purdom 1970 $O(V^{2}+VE)$ $O(V^{2})$ Exact Deterministic Time & Space

Time Complexity Graph

Strongly Connected Components - Transitive Closure - Time.png