Subtree Isomorphism is in Random NC

TitleSubtree Isomorphism is in Random NC
Publication TypeTechnical Report
Year of Publication1989
AuthorsGibbons, P. B., Karp R. M., Miller G. L., & Soroker D.
Other Numbers513

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(log(superscript 3)n) 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.

Bibliographic Notes

ICSI Technical Report TR-89-014

Abbreviated Authors

P. Gibbons, R. M. Karp, G. L. Miller, and D. Soroker

ICSI Publication Type

Technical Report