# 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