Subtree isomorphism is in random NC

Phillip B. Gibbons, Richard M. Karp, Gary L. Miller, Danny Soroker

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(log3 n) on a CREW PRAM, where n is the number of nodes in H. 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.
BibTeX
@inproceedings{gibbons1990subtree,
  author = {Phillip B. Gibbons and Richard M. Karp and Gary L. Miller and Danny Soroker},
  title = {{Subtree isomorphism is in random NC}},
  booktitle = {Discret. Appl. Math},
  year = {1990},
  url = {https://openreview.net/forum?id=LP8hrX0hAYU},
}

Loading related content...

Figure