Robert Manson Sawko, Malgorzata Zimon
SIAM/ASA JUQ
Given two trees, a guest tree G and a host tree H, the subtree isomorphism problem is to determine whether there is a subgraph of H that is isomorphic to G. We present a randomized parallel algorithm for finding such an isomorphism, if it exists. The algorithm runs in time O(log3n) on a CREW PRAM, where n is the number of nodes in H. The number of processors required by the algorithm is polynomial in n. Randomization is used (solely) to solve each of a series of bipartite matching problems during the course of the algorithm. We demonstrate the close connection between the two problems by presenting a log-space reduction from bipartite perfect matching to subtree isomorphism. Finally, we present some techniques to reduce the number of processors used by the algorithm. © 1990.
Robert Manson Sawko, Malgorzata Zimon
SIAM/ASA JUQ
M. Shub, B. Weiss
Ergodic Theory and Dynamical Systems
F.M. Schellenberg, M. Levenson, et al.
BACUS Symposium on Photomask Technology and Management 1991
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences