Randomized parallel algorithm for planar graph isomorphism


Journal Article

We present a parallel randomized algorithm for finding if two planar graphs are isomorphic. Assuming that we have a tree of separators for each planar graph, our algorithm takes O(log(n)) time with P = (n1.5·√log(n)) processors with probability to fail of 1/n or less, where n is the number of vertices. The algorithms 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 processors number to n3/2+ε. This algorithm significantly improves the previous results of n4 processors.

Duke Authors

Cited Authors

  • Gazit, H; Reif, JH

Published Date

  • December 1, 1990

Published In

  • Algorithms and Architectures

Start / End Page

  • 210 - 219

Citation Source

  • Scopus