The Polynomially Bounded Perfect Matching Problem Is in NC 2
From MaRDI portal
Publication:3590959
DOI10.1007/978-3-540-70918-3_42zbMath1186.68216OpenAlexW1545592468MaRDI QIDQ3590959
Thanh Minh Hoang, Thomas Thierauf, Manindra Agrawal
Publication date: 3 September 2007
Published in: STACS 2007 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-70918-3_42
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (8)
NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ Unnamed Item ⋮ A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs ⋮ Unnamed Item ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
This page was built for publication: The Polynomially Bounded Perfect Matching Problem Is in NC 2
