Abstract
An algorithm is given for computing the transitive closure of a directed graph in a time no greater thana 1 N 1 n+a 2 n 2 for largen wherea 1 anda 2 are constants depending on the computer used to execute the algorithm,n is the number of nodes in the graph andN 1 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 probabilityp, the average time to compute the transitive closure is no greater than min{a 1 pn 3+a 2 n 2, 1/2a 1 n 2 p −2+a 2 n 2} for largen. The algorithm will compute the transitive closure of an undirected graph in a time no greater thana 2 n 2 for largen. The method uses aboutn 2+n bits and 5n words of storage (where each word can holdn+2 values).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Warshall, Stephen,A Theorem on Boolean Matrices, JACM 9 (1962), 11–12.
Thorelli, Lars-Erik,An Algorithm for Computing All Paths in a Graph, BIT 6 (1966), 347–349.
Wirth, Niklaus and Weber, Helmut,Euler: A Generalization of ALGOL, and its Formal Definition, CACM 9, 13–25 and 89–99.
Lynch, W. C.,Ambiguities in BNF Languages thesis, Univ. of Wisconsin, 1963 andA High-Speed Parsing Algorithm for ICOR Grammars, 1968, Report No. 1097, Computing Center, Case Western Reserve University.
Knuth, Donald,The Art of Computer Programming, Vol. 1, Addison-Wesley, Reading, Mass., 1968, pp. 258–268.
Kahn, A. B.,Topological Sorting of Large Networks, CACM 5 (1962), 558–562.
Purdom, Paul W.,A Transitive Closure Algorithm, July 1968, Computer Sciences Technical Report #33, University of Wisconsin.
Palasti, I.,On the strong Connectedness of Directed Random Graphs, Studia Scientiarum Mathematicarum Hungarica 1 (1966), 205–214.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Purdom, P. A transitive closure algorithm. BIT 10, 76–94 (1970). https://doi.org/10.1007/BF01940892
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01940892