Publications [#236971] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Gazit, H; Reif, JH, A Randomized Parallel Algorithm for Planar Graph Isomorphism, Journal of Algorithms, vol. 28 no. 2 (January, 1998), pp. 290-314, Elsevier BV [doi]
   (last updated on 2026/01/14)

   Abstract:
   We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms in O(log² n) time with n^1+ε processors, for any ε > O). If n is the number of vertices, our algorithm takes O(log(n)) time with P = O(n^1.5 · √log(n)) processors and with a probability of failure of 1/n at most. The algorithm needs 2 · log(m) - log(n) + O(log(n)) random bits. The number of random bits can be decreased to O(log(n)) by increasing the number of processors to n^3/2+ε, for any ε > 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput. 20 (1991), 1128-1147), which requires n⁴ randomized processors or n⁵ deterministic processors. © 1998 Academic Press.