Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem

DOI10.1016/0022-0000(92)90005-4zbMath0743.68072OpenAlexW1964011448MaRDI QIDQ1185245

Elias Dahlhaus, Marek Karpinski

Publication date: 28 June 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90005-4

zbMATH Keywords

parallel complexityperfect matchingPeterson's theorem

Mathematics Subject Classification ID

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

Related Items (5)

Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs ⋮ The computational complexity of graph problems with succinct multigraph representation ⋮ Computational complexity of three-dimensional discrete tomography with missing data ⋮ Approximating the permanent of graphs with large factors ⋮ Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• Matching is as easy as matrix inversion
• Subtree isomorphism is NC reducible to bipartite perfect matching
• A taxonomy of problems with fast parallel algorithms
• A fast parallel algorithm for routing in permutation networks
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems

This page was built for publication: Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem