Subtree Isomorphism is in Random NC

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

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-87-389

, 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},
    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