Subtree isomorphism is in random NC

DOI10.1016/0166-218X(90)90081-MMaRDI QIDQ922707zbMATH OpenFDO

Authors Phillip B. Gibbons, Richard Karp, Danny Soroker, Gary L. Miller

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

CREW PRAMrandomized parallel algorithmssubtree isomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• 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

Cites work

• 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?)
• An Efficient Parallel Biconnectivity Algorithm
• An improved parallel processor bound in fast matrix inversion
• Constructing a perfect matching is in random NC
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast parallel matrix and GCD computations
• 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

Cited in

(8)

• On an algorithm of Zemlyachenko for subtree isomorphism
• Sequential and parallel algorithms for embedding problems on classes of partial k-trees
• Finding smallest supertrees
• Approximate labelled subtree homeomorphism
• scientific article; zbMATH DE number 4064509 (Why is no real title available?)
• Isomorphism testing of k-trees is in NC, for fixed k
• The parallel complexity of tree embedding problems (extended abstract)
• Subtree isomorphism is NC reducible to bipartite perfect matching

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)