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

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

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)

• Constructing a perfect matching is in random NC
• Isolation, matching, and counting uniform and nonuniform upper bounds
• A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
• On the parameterized parallel complexity and the vertex cover problem
• Parity separation: a scientifically proven method for permanent weight loss
• Bipartite perfect matching is in quasi-NC
• Isolating a vertex via lattices: polytopes with totally unimodular faces
• NC algorithms for weighted planar perfect matching and related problems
• Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
• Planar graph perfect matching is in NC
• A unified method for placing problems in polylogarithmic depth
• Bipartite perfect matching is in quasi-NC
• Algorithms – ESA 2004
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3590959)