The Polynomially Bounded Perfect Matching Problem Is in NC 2
DOI10.1007/978-3-540-70918-3_42zbMATH Open1186.68216OpenAlexW1545592468MaRDI QIDQ3590959FDOQ3590959
Authors: Thanh Minh Hoang, Manindra Agrawal, Thomas Thierauf 
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 (14)
- Planar graph perfect matching is in NC
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Bipartite perfect matching is in quasi-NC
- Parity separation: a scientifically proven method for permanent weight loss
- Bipartite perfect matching is in quasi-NC
- Constructing a perfect matching is in random NC
- A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
- NC algorithms for weighted planar perfect matching and related problems
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- A unified method for placing problems in polylogarithmic depth
- On the parameterized parallel complexity and the vertex cover problem
- 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)
