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