Subtree isomorphism is in random NC
Lists
Only you see this
Abstract
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(log3 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 bipartite perfect matching to subtree isomorphism. Finally, we present some techniques to reduce the number of processors used by the algorithm.
BibTeX
@inproceedings{gibbons1990subtree,
author = {Phillip B. Gibbons and Richard M. Karp and Gary L. Miller and Danny Soroker},
title = {{Subtree isomorphism is in random NC}},
booktitle = {Discret. Appl. Math},
year = {1990},
url = {https://openreview.net/forum?id=LP8hrX0hAYU},
}Loading related content...