Algorithms for transitive closure
Let sigma'(n) denote the number of all strongly connected graphs on the n-element set. We prove that sigma'(n) greater than or equal to 2(n2) (1- n(n - 1)/2(n-1)). Hence the algorithm computing a transitive closure by a reduction to acyclic graphs has the expected time O(n(2)), under the assumption of uniform distribution of input graphs. Furthermore, we present a new algorithm constructing the transitive closure of an acyclic graph. (C) 2002 Elsevier Science B.V. All rights reserved.
algorithms transitive closure computational complexity graph algorithms