Bipartite Perfect Matching in Pseudo-Deterministic NC
From MaRDI portal
Publication:5111418
DOI10.4230/LIPIcs.ICALP.2017.87zbMath1442.68167OpenAlexW2740009680MaRDI QIDQ5111418
Ofer Grossman, Shafi Goldwasser
Publication date: 27 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7482/pdf/LIPIcs-ICALP-2017-87.pdf/
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (10)
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 ⋮ On Pseudodeterministic Approximation Algorithms. ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Bipartite Perfect Matching is in Quasi-NC
This page was built for publication: Bipartite Perfect Matching in Pseudo-Deterministic NC
