New answers tagged

2 votes
Accepted

Transitive Closure of a graph

Using Kosaraju's algorithm, you can compute the strongly connected components (SCC) of $G$ in linear time. The metagraph (or graph of the SCC) is well known to be a DAG. You can then compute the ...
user avatar
  • 7,047

Top 50 recent answers are included