## Randomized parallel algorithm for planar graph isomorphism

Publication
, Journal Article

Gazit, H; Reif, JH

Published in: Algorithms and Architectures

December 1, 1990

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 Scholars

## Published In

Algorithms and Architectures

## Publication Date

December 1, 1990

## Start / End Page

210 / 219

### Citation

APA

Chicago

ICMJE

MLA

NLM

Gazit, H., & Reif, J. H. (1990). Randomized parallel algorithm for planar graph isomorphism.

*Algorithms and Architectures*, 210–219.Gazit, H., and J. H. Reif. “Randomized parallel algorithm for planar graph isomorphism.”

*Algorithms and Architectures*, December 1, 1990, 210–19.Gazit H, Reif JH. Randomized parallel algorithm for planar graph isomorphism. Algorithms and Architectures. 1990 Dec 1;210–9.

Gazit, H., and J. H. Reif. “Randomized parallel algorithm for planar graph isomorphism.”

*Algorithms and Architectures*, Dec. 1990, pp. 210–19.Gazit H, Reif JH. Randomized parallel algorithm for planar graph isomorphism. Algorithms and Architectures. 1990 Dec 1;210–219.

## Published In

Algorithms and Architectures

## Publication Date

December 1, 1990

## Start / End Page

210 / 219