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. I deleted my earlier post to this group because it came in as a reply to a different post. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
