Subtree Isomorphism is in Random NC

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

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-389
December 1987

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-389.pdf

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^3 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 perfect bipartite matching to subtree isomorphism. Finally, we present some techniques to reduce the number of processors used by the algorithm.


BibTeX citation:

@techreport{Gibbons:CSD-87-389,
    Author = {Gibbons, Phillip B. and Karp, Richard M. and Miller, Gary L. and Soroker, Danny},
    Title = {Subtree Isomorphism is in Random NC},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1987},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5291.html},
    Number = {UCB/CSD-87-389},
    Abstract = {Given two trees, a guest tree <i>G</i> and a host tree <i>H</i>, the subtree isomorphism problem is to determine whether there is a subgraph of <i>H</i> that is isomorphic to <i>G</i>. We present a randomized parallel algorithm for finding such an isomorphism, if it exists. The algorithm runs in time <i>O</i>(log^3 <i>n</i>) on a CREW PRAM, where <i>n</i> is the number of nodes in <i>H</i>. 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 perfect bipartite matching to subtree isomorphism. Finally, we present some techniques to reduce the number of processors used by the algorithm.}
}

EndNote citation:

%0 Report
%A Gibbons, Phillip B.
%A Karp, Richard M.
%A Miller, Gary L.
%A Soroker, Danny
%T Subtree Isomorphism is in Random NC
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-389
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5291.html
%F Gibbons:CSD-87-389