Bipartite Perfect Matching is in Quasi-NC
DOI10.1137/16M1097870zbMath1464.68126OpenAlexW2981568733WikidataQ126979509 ScholiaQ126979509MaRDI QIDQ4997314
Rohit Gurjar, Thomas Thierauf, Stephen A. Fenner
Publication date: 29 June 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1097870
parallel algorithmsbipartite graphsparallel complexityderandomizationperfect matchinggraph matchingisolation lemmamatching polytopequasi-NC
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 (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Green's theorem and isolation in planar graphs
- On computing the determinant in small parallel time using a small number of processors
- Matching theory
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- Subtree isomorphism is NC reducible to bipartite perfect matching
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- A probabilistic remark on algebraic program testing
- Matching and multidimensional matching in chordal and strongly chordal graphs
- Tight bounds and conjectures for the isolation lemma
- Deterministically isolating a perfect matching in bipartite planar graphs
- Parallel Depth-First Search in General Directed Graphs
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
- The Polynomially Bounded Perfect Matching Problem Is in NC 2
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Log Depth Circuits for Division and Related Problems
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Parallel Matrix and Graph Algorithms
- On Chebyshev-Type Inequalities for Primes
- The number of shortest cycles and the chromatic uniqueness of a graph
- Fast Parallel Matrix Inversion Algorithms
- An $\NC$ Algorithm for Minimum Cuts
- Flow in Planar Graphs with Multiple Sources and Sinks
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Exact Perfect Matching in Complete Graphs
- Linear matroid intersection is in quasi-NC
- Bipartite Perfect Matching in Pseudo-Deterministic NC
- Planar Graph Perfect Matching Is in NC
- Randomness efficient identity testing of multivariate polynomials
- Paths, Trees, and Flowers
- Bipartite perfect matching is in quasi-NC
- Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
This page was built for publication: Bipartite Perfect Matching is in Quasi-NC
