best known transitive closure algorithm for graph

Question

In terms of runtime, what is the best known transitive closure algorithm for directed graphs?

I am currently using Warshall's algorithm but its O(n^3). Although, due to the graph representation my implementation does slightly better (instead of checking all edges, it only checks all out going edges). Is there any transitive closure algorithm which is better than this? In particular, is there anything specifically for shared memory multi-threaded architectures?

Thanks in advance.

Raghava.

Answer 1

The Algorithm Design manual has some useful information. Key points:

• Transitive closure is as difficult as matrix multiplication; so the best known bound is the Coppersmith–Winograd algorithm which runs in O(n^2.376), but in practice it's probably not worthwhile to use matrix multiplication algorithms.
• For a heuristic speedup, calculate strongly connected components first.