Subtree isomorphism is in random NC
A subtree isomorphism problem is to determine for given two trees G and H whether there is a subgraph (subtree) of H that is isomorphic to G. Unlike other versions of the (sub)graph isomorphism problem this one is known to be in P, yet the existence of a fast parallel algorithm to solve it posses an interesting problem. The authors answer this problem affirmatively, provided that we consider randomized parallel algorithms. Their algorithm runs in time \(O(\log^ 3 n)\) on a CREW PRAM using \(n^ 3M(n)\log \log n/\log n\) processors, where M(n) is the number of bit operations required by a CREW PRAM to multiply two \(n\times n\) boolean matrices in O(log n) time. The authors start with the description of an algorithm for solving the rooted version of the subtree isomorphism problem, whic is then extended to the general unrooted case. Their approach is based on the best known sequential algorithm for this problem, given by \textit{D. W. Matula} [Annals of Discrete Mathematics 2, 91-106 (1978; Zbl 0391.05022)], combined with the dynamic contraction technique by \textit{G. L. Miller} and \textit{J. H. Reif} [Parallel tree contraction and its application, Proc. Symp. on Foundations of Computer Science, 478-489 (1985)]. The randomized part of their algorithm is derived from using the randomized algorithm of \textit{K. Mulmuley}, \textit{U. V. Vazirani} and \textit{V. V. Vazirani} [Combinatorica 7(1), 105-113 (1987; Zbl 0632.68041)] for constructing a perfect matching in a bipartite graph. Finally they prove that bipartite perfect matching is log-space irreducible to subtree isomorphism.
- scientific article; zbMATH DE number 4064509
- Faster Subtree Isomorphism
- A note on the subtree isomorphism for ordered trees and related problems
- Subtree isomorphism is NC reducible to bipartite perfect matching
- Parallel Tree Contraction Part 2: Further Applications
- Finding largest subtrees and smallest supertrees
- Further comments on the subtree isomorphism for ordered trees
- scientific article; zbMATH DE number 4213471
- Subtree isomorphism revisited
- Subtree isomorphism revisited
- An Efficient Parallel Biconnectivity Algorithm
- An improved parallel processor bound in fast matrix inversion
- Constructing a perfect matching is in random NC
- Fast parallel matrix and GCD computations
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- scientific article; zbMATH DE number 3965444 (Why is no real title available?)
- scientific article; zbMATH DE number 4064509 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Improved processor bounds for combinatorial problems in RNC
- Matching is as easy as matrix inversion
- Maximum matchings in general graphs through randomization
- Parallel Prefix Computation
- Simulation of Parallel Random Access Machines by Circuits
- Subtree Isomorphism in O(n5/2)
- Subtree isomorphism is NC reducible to bipartite perfect matching
- Systems of distinct representatives and linear algebra
- The Parallel Evaluation of General Arithmetic Expressions
- Approximate labelled subtree homeomorphism
- Subtree isomorphism is NC reducible to bipartite perfect matching
- On an algorithm of Zemlyachenko for subtree isomorphism
- scientific article; zbMATH DE number 4064509 (Why is no real title available?)
- SUBTREE ISOMORPHISM IS IN DLOG FOR NESTED TREES
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees
- The parallel complexity of tree embedding problems (extended abstract)
- Finding smallest supertrees
- Isomorphism testing of k-trees is in NC, for fixed k
This page was built for publication: Subtree isomorphism is in random NC
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q922707)
