Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
From MaRDI portal
Publication:1185245
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
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
