A Randomized Parallel Algorithm for Planar Graph Isomorphism

Published

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Gazit, H; Reif, JH

Published Date

  • January 1, 1998

Published In

Volume / Issue

  • 28 / 2

Start / End Page

  • 290 - 314

International Standard Serial Number (ISSN)

  • 0196-6774

Digital Object Identifier (DOI)

  • 10.1006/jagm.1998.0943

Citation Source

  • Scopus