The Polynomially Bounded Perfect Matching Problem Is in NC 2
DOI10.1007/978-3-540-70918-3_42zbMATH Open1186.68216OpenAlexW1545592468MaRDI QIDQ3590959FDOQ3590959
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
Recommendations
- Planar graph perfect matching is in NC
- Constructing a perfect matching is in random NC
- Some perfect matchings and perfect half-integral matchings in NC
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- scientific article; zbMATH DE number 4062621
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)
Cited In (11)
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- On the Parameterized Parallel Complexity and the Vertex Cover Problem
- NC Algorithms for Weighted Planar Perfect Matching and Related Problems
- Bipartite Perfect Matching is in Quasi-NC
- Title not available (Why is that?)
- Title not available (Why is that?)
- Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
- Constructing a perfect matching is in random NC
- A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Algorithms – ESA 2004
This page was built for publication: The Polynomially Bounded Perfect Matching Problem Is in NC 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3590959)
