×

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.

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