Subtree isomorphism is in random NC

DOI10.1016/0166-218X(90)90081-MzbMath0711.68052MaRDI QIDQ922707

Phillip B. Gibbons, Danny Soroker, Richard M. Karp, Gary Lee Miller

Publication date: 1990

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

zbMATH Keywords

randomized parallel algorithmsCREW PRAMsubtree 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)

Related Items

Sequential and parallel algorithms for embedding problems on classes of partial k-trees, The parallel complexity of tree embedding problems (extended abstract), Approximate labelled subtree homeomorphism

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• Subtree isomorphism is NC reducible to bipartite perfect matching
• An improved parallel processor bound in fast matrix inversion
• Improved processor bounds for combinatorial problems in RNC
• Maximum matchings in general graphs through randomization
• Simulation of Parallel Random Access Machines by Circuits
• An Efficient Parallel Biconnectivity Algorithm
• Parallel Prefix Computation
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Subtree Isomorphism in O(n5/2)
• The Parallel Evaluation of General Arithmetic Expressions
• Fast parallel matrix and GCD computations
• Systems of distinct representatives and linear algebra