Subtree isomorphism is in random NC
type: Item
instance of: scholarly article
title: Subtree isomorphism is in random NC
zbMATH Open document ID: 0711.68052
DOI: 10.1016/0166-218X(90)90081-M
author: Phillip B. Gibbons
author: Richard Karp
author: Danny Soroker
author: Gary L. Miller
published in: Discrete Applied Mathematics
publication date: 1990-01-01T00:00:00Z
review text: 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.
reviewed by: Jozef Vyskoč
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4170097
zbMATH Keywords: subtree isomorphism problem
zbMATH Keywords: randomized parallel algorithms
zbMATH Keywords: CREW PRAM
MaRDI profile type: Publication
cites work: Fast parallel matrix and GCD computations
cites work: The Parallel Evaluation of General Arithmetic Expressions
cites work: Systems of distinct representatives and linear algebra
cites work: Improved processor bounds for combinatorial problems in RNC
cites work: Q4198056
cites work: Q3798258
cites work: Constructing a perfect matching is in random NC
cites work: Subtree isomorphism is NC reducible to bipartite perfect matching
cites work: Parallel Prefix Computation
cites work: Subtree Isomorphism in O(n5/2)
cites work: Matching is as easy as matrix inversion
cites work: Q3732964
cites work: An improved parallel processor bound in fast matrix inversion
cites work: Maximum matchings in general graphs through randomization
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: Simulation of Parallel Random Access Machines by Circuits
cites work: An Efficient Parallel Biconnectivity Algorithm
Recommended article: Q3798258
Recommended article: Faster Subtree Isomorphism
Recommended article: A note on the subtree isomorphism for ordered trees and related problems
Recommended article: Subtree isomorphism is NC reducible to bipartite perfect matching
Recommended article: Parallel Tree Contraction Part 2: Further Applications
Recommended article: Finding largest subtrees and smallest supertrees
Recommended article: Further comments on the subtree isomorphism for ordered trees
Recommended article: Q3359785
Recommended article: Subtree Isomorphism Revisited
description: scientific article; zbMATH DE number 4170097