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