Subtree isomorphism is NC reducible to bipartite perfect matching

DOI10.1016/0020-0190(89)90170-1zbMath0664.68072OpenAlexW2045160990MaRDI QIDQ1115630

Marek Karpinski, Andrzej Lingas

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90170-1

zbMATH Keywords

bipartite graphperfect matchingparallel random access machineNC-reducibilitysubtree isomorphism

Mathematics Subject Classification ID

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

Related Items

Sequential and parallel algorithms for embedding problems on classes of partial k-trees, Subtree isomorphism is NC reducible to bipartite perfect matching, Some complexity theoretic aspects of AC rewriting, The parallel complexity of tree embedding problems (extended abstract), Maximum tree-packing in time \(O(n^{5/2})\), Maximum tree-packing in time O(n5/2), Subtree isomorphism is in random NC, Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time, Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem, Tight complexity bounds for term matching problems, Approximate labelled subtree homeomorphism, Derandomizing Isolation in Space-Bounded Settings, Bipartite Perfect Matching is in Quasi-NC

Cites Work

• Unnamed Item
• Unnamed Item
• Matching is as easy as matrix inversion
• Subtree isomorphism is NC reducible to bipartite perfect matching
• On uniform circuit complexity
• Parallel concepts in graph theory
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Simulation of Parallel Random Access Machines by Circuits
• A taxonomy of problems with fast parallel algorithms
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• A Separator Theorem for Planar Graphs
• An Analysis of a Good Algorithm for the Subtree Problem
• Subtree Isomorphism in O(n5/2)