Hi all, 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. PS: I posted this question at http://stackoverflow.com/questions/3517524/best-known-transitive-closure-algorithm-for-graph. Reposting it here, so that I may get more responses. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
