{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,19]],"date-time":"2026-10-19T21:11:39Z","timestamp":1792444299640,"version":"4.5.0"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1991,2]]},"abstract":"<jats:p>There is a straightforward algorithm for computing the transitive-closure of an n-node graph in $O(\\log ^2 n)$ time on an EREW-PRAM, using $n^3 \/ \\log n$ processors, or indeed with $M(n) \/ \\log n$ processors if serial matrix multiplication in $M(n)$ time can be done. This algorithm is within a log factor of optimal in work (processor-time product), for solving the all-pairs transitive-closure problem for dense graphs. However, this algorithm is far from optimal when either (a) the graph is sparse, or (b) we want to solve the single-source transitive-closure problem. It would be ideal to have an $\\mathcal{NC}$ algorithm for transitive-closure that took about e processors for the single-source problem on a graph with n nodes and $e \\geqq n$ arcs, or about $en$ processors for the all-pairs problem on the same graph. While an algorithm that good cannot be offered, algorithms with the following performance can be offered. (1) For single-source, $\\tilde{O}(n^\\varepsilon )$ time with $\\tilde O(en^{1 - 2\\varepsilon } )$ processors, provided $e &gt; n^{2 - 3\\varepsilon } $, and (2) forall-pairs, $\\tilde{O}(n^\\varepsilon )$ time and $\\tilde O(en^{1 - \\varepsilon } )$ processors, provided $e \\geqq n^{2 - 2\\varepsilon } $. Each of these claims assumes that $0 &lt; \\varepsilon \\leqq \\frac{1}{2}$. Importantly, the algorithms are (only) high-probability algorithms; that is, if they find a path, then a path exists, but they may fail to find a path that exists with probability at most $2^{ - \\alpha c} $, where $\\alpha $ is some positive constant, and c is a multiplier for the time taken by the algorithm. However, it is shown that incorrect results can be detected, thus putting the algorithm in the \u201cLas Vegas\u201d class. Finally, it is shown how to do \u201cbreadth-first-search\u201d with the same performance as can be achieved for single-source transitive closure.<\/jats:p>","DOI":"10.1137\/0220006","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:34:57Z","timestamp":1109226897000},"page":"100-125","source":"Crossref","is-referenced-by-count":105,"title":["High-Probability Parallel Transitive-Closure Algorithms"],"prefix":"10.1137","volume":"20","author":[{"given":"Jeffrey D.","family":"Ullman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","unstructured":"P. A. Bloniarz, M. J. Fischer, A. R. Meyer,  A note on the average time to compute transitive closure,  3rd Internat. Colloquium on Automata, Languages, and Programming, Edinburgh, U.K., Springer-Verlag, Berlin, New York,  1976 0363.68055"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Z. Broder, A. R. Karlin, P. Raghavan, E. Upfal,  Trading space for time in undirected  s- t connectivity,  Proc. 21st annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1989","DOI":"10.1145\/73007.73059"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"R. Cole, U. Vishkin,  Approximate and exact parallel scheduling with applications to list, tree, and graph problems,  Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC,  1986,  478\u2013491","DOI":"10.1109\/SFCS.1986.10"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, S. Winograd,  Matrix multiplication via arithmetic progressions,  Proc. 19th Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York,  1987,  1\u20136","DOI":"10.1145\/28395.28396"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"H. Gazit,  An optimal randomized parallel algorithm for finding connected components in a graph,  Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC,  1986,  492\u2013501","DOI":"10.1109\/SFCS.1986.9"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90164-0"},{"key":"R9","unstructured":"Daniel H. Greene, Donald E. Knuth, Mathematics for the analysis of algorithms, Progress in Computer Science, Vol. 1, Birkh\u00e4user Boston, Mass., 1981, 107\u201383c:680450481.68042"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0207011"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90008-6"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-16761-7_87"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0220006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:30Z","timestamp":1787337810000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0220006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,2]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,2]]}},"alternative-id":["10.1137\/0220006"],"URL":"https:\/\/doi.org\/10.1137\/0220006","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,2]]}}}