Paul Purdom (Transitive Closure Strongly Connected Components)

Time Complexity

$O(V^{2}+VE)$

Space Complexity

$O(V^{2})$ words

(https://link.springer.com/content/pdf/10.1007/BF01940892.pdf)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1970

Reference

https://link.springer.com/article/10.1007%2FBF01940892