zbMATH — the first resource for mathematics

Subtree isomorphism is in random NC. (English) Zbl 0652.68078
VLSI algorithms and architectures, Proc. 3rd Aegean Workshop Comput., Corfu/Greece 1988, Lect. Notes Comput. Sci. 319, 43-52 (1988).
[For the entire collection see Zbl 0643.00025.]
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 bipartite perfect matching to subtree isomorphism. Finally, we present some techniques to reduce the number of processors used by the algorithm.

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)