Publications [#236941] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Miller, GL; Reif, JH, Parallel tree contraction. Part 2. Further applications, SIAM Journal on Computing, vol. 20 no. 6 (January, 1991), pp. 1128-1147, Society for Industrial & Applied Mathematics (SIAM) [doi]
   (last updated on 2026/01/15)

   Abstract:
   This paper applies the parallel tree contraction techniques developed in Miller and Reif's paper [Randomness and Computation, Vol. 5, S. Micali, ed., JAI Press, 1989, pp. 47-72] to a number of fundamental graph problems. The paper presents an O(log n) time and n/log n processor, a 0-sided randomized algorithm for testing the isomorphism of trees, and an O(log n) time, n-processor algorithm for maximal subtree isomorphism and for common subexpression elimination. An O(log n) time, n-processor algorithm for computing the canonical forms of trees and subtrees is given. An Olog n time algorithm for computing the tree of 3-connected components of a graph, an O(log² n) time algorithm for computing an explicit planar embedding of a planar graph, and an O(log³ n) time algorithm for computing a canonical form for a planar graph are also given. All these latter algorithms use only n^O(1) processors on a Parallel Random Access Machine (PRAM) model with concurrent writes and concurrent reads.