Subtree Isomorphism is in Random NC
Title | Subtree Isomorphism is in Random NC |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Gibbons, P. B., Karp R. M., Miller G. L., & Soroker D. |
Other Numbers | 513 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-89-014.pdf |
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 |