Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1987/5291.html
%F Gibbons:CSD-87-389