R.A. Brualdi, A.J. Hoffman
Linear Algebra and Its Applications
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(log3n) on a CREW PRAM, where n is the number of nodes in H. The number of processors required by the algorithm is polynomial in n. 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 bipartite perfect matching to subtree isomorphism. Finally, we present some techniques to reduce the number of processors used by the algorithm. © 1990.
R.A. Brualdi, A.J. Hoffman
Linear Algebra and Its Applications
Jaione Tirapu Azpiroz, Alan E. Rosenbluth, et al.
SPIE Photomask Technology + EUV Lithography 2009
Simeon Furrer, Dirk Dahlhaus
ISIT 2005
Laxmi Parida, Pier F. Palamara, et al.
BMC Bioinformatics