## Parallel tree contraction. Part 2. Further applications

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(log2 n) time algorithm for computing an explicit planar embedding of a planar graph, and an O(log3 n) time algorithm for computing a canonical form for a planar graph are also given. All these latter algorithms use only nO(1) processors on a Parallel Random Access Machine (PRAM) model with concurrent writes and concurrent reads.

### Duke Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics

### Citation

*SIAM Journal on Computing*,

*20*(6), 1128–1147. https://doi.org/10.1137/0220070

*SIAM Journal on Computing*20, no. 6 (January 1, 1991): 1128–47. https://doi.org/10.1137/0220070.

*SIAM Journal on Computing*, vol. 20, no. 6, Jan. 1991, pp. 1128–47.

*Scopus*, doi:10.1137/0220070.

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics