The Polynomially Bounded Perfect Matching Problem Is in NC 2

DOI10.1007/978-3-540-70918-3_42MaRDI QIDQ3590959zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

Cited in

(14)

• Algorithms – ESA 2004
• 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
• Isolation, matching, and counting uniform and nonuniform upper bounds
• NC algorithms for weighted planar perfect matching and related problems
• 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

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)