A Randomized Parallel Algorithm for Planar Graph Isomorphism

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(log2 n) time with n1+ε processors, for any ε > O). If n is the number of vertices, our algorithm takes O(log(n)) time with P = O(n1.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 n3/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 n4 randomized processors or n5 deterministic processors. © 1998 Academic Press.

Duke Scholars

Author John H. Reif Computer Science