A Transitive Closure Algorithm

File(s)
Date
1968Author
Purdom, Paul W.
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
An algorithm is given for computing the transitive closure of a directed
graph in a time no greater than a1 N1 n + a2n2 for large n where a1 and a2
are constants depending on the computer used to execute the algorithm, n is the number of nodes in the graph and N1 is the number of arcs (not counting those arcs which are part of a cycle and not counting those arcs which can be removed without changing the transitive closure). For graphs where each arc is selected at random with probability p , the average time to compute the transitive closure is no greater than min {a1 pn3 + a2n2, 1/2a1n2p-2+a2n2} for large n . The algorithm will compute the transitive closure of an undirected graph in a time no greater than a2n2 for large n. The method uses about n2 + n bits and 5n words of storage (where each word can hold n + 2 values).
Permanent Link
http://digital.library.wisc.edu/1793/57514Citation
TR33