Subtree isomorphism is NC reducible to bipartite perfect matching

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

Andrzej Lingas, Marek Karpinski

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 graph; perfect matching; parallel random access machine; NC-reducibility; subtree isomorphism

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Subtree isomorphism is in random NC, Approximate labelled subtree homeomorphism, Subtree isomorphism is NC reducible to bipartite perfect matching, Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem, Tight complexity bounds for term matching problems, Maximum tree-packing in time \(O(n^{5/2})\), Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time

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)