The transitive closure of a graph is defined e. g. here: http://mathworld.wolfram.com/TransitiveClosure.html
It is easily possible in O(n^3), where n is the number of vertices. I was wondering if it can be done in time O(n^2).
Thanks in advance
+2
A:
Nope. I don't think there is a O(n2) algorithm for it. I would expect if such an algorithm existed, you could solve all pair shortest paths problem in O(n2) too, which is not the case. The asymptotically fastest algorithm I can think of is an implementation of Dijkstra's shortest path algorithm with a Fibonacci heap (O(n2log n) in not very dense graphs).
Mehrdad Afshari
2009-04-01 00:02:10
+1
A:
Hmm. I found an algorithm that computes the transitive closure in O(n^2) EXPECTED run time.
nes1983
2009-04-01 00:08:49
with which random distribution?
jpalecek
2009-04-01 00:18:51
no idea. i don't want to use it, because i don't want any randomization in my surrounding algorithm. it's here: http://www.springerlink.com/content/f511w61n62l17168/
nes1983
2009-04-05 18:33:08
+1
A:
Given that this:
Can you come up with an O(kn^2 + m) transitive closure/reduction algorithm, where k is the number of missing/extra edges in the transitive closure/reduction?
Is still considered an open question by people who think about these sorts of things more than we do, I'd say "I don't know".
(But if you solve it and want a PhD, I know that algorithm.)
MarkusQ
2009-04-01 00:09:22