CH Algorithm (SCCs Strongly Connected Components)
Jump to navigation
Jump to search
Time Complexity
$O(VE)$
Space Complexity
$O(V+E)$? words
(Each vertex needs to keep track of one color; then we need to build recursive subgraphs)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2004
Reference
https://research.vu.nl/en/publications/on-distributed-verification-and-verified-distribution