Bipartite perfect matching is in quasi-NC

DOI10.1145/2897518.2897564zbMath1373.68267arXiv1601.06319OpenAlexW2399980850MaRDI QIDQ5361877

Rohit Gurjar, Stephen A. Fenner, Thomas Thierauf

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1601.06319

zbMATH Keywords

parallel complexityderandomizationgraph matchingquasi-NC

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20)

Related Items (23)

NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ Unnamed Item ⋮ On the parallel complexity of constrained read-once refutations in UTVPI constraint systems ⋮ A deterministic parallel reduction from weighted matroid intersection search to decision ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sylvester-Gallai type theorems for quadratic polynomials ⋮ Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization ⋮ Linear matroid intersection is in quasi-NC ⋮ Unnamed Item ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Operator scaling: theory and applications ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes ⋮ Unnamed Item ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ Improved hitting set for orbit of ROABPs ⋮ A real polynomial for bipartite graph minimum weight perfect matchings ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

This page was built for publication: Bipartite perfect matching is in quasi-NC