Publications [#236932] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Gazit, H; Reif, JH, Randomized parallel algorithm for planar graph isomorphism, Algorithms and Architectures (December, 1990), pp. 210-219
   (last updated on 2026/01/15)

   Abstract:
   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 = (n^1.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 n^3/2+ε. This algorithm significantly improves the previous results of n⁴ processors.