Bipartite perfect matching in pseudo-deterministic NC

DOI10.4230/LIPICS.ICALP.2017.87zbMATH Open1442.68167OpenAlexW2740009680MaRDI QIDQ5111418FDOQ5111418

Authors: 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/

Recommendations

• Constructing a perfect matching is in random NC
• Bipartite perfect matching is in quasi-NC
• Bipartite perfect matching is in quasi-NC
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• Planar graph perfect matching is in NC

zbMATH Keywords

parallel algorithmsperfect matchingRNCpseudo-determinism

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Cited In (10)

• On Pseudodeterministic Approximation Algorithms.
• Title not available (Why is that?)
• NC Algorithms for Weighted Planar Perfect Matching and Related Problems
• Bipartite Perfect Matching is in Quasi-NC
• Title not available (Why is that?)
• Title not available (Why is that?)
• Planar Maximum Matching: Towards a Parallel Algorithm
• NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
• On the parallel complexity of constrained read-once refutations in UTVPI constraint systems
• A deterministic parallel reduction from weighted matroid intersection search to decision

This page was built for publication: Bipartite perfect matching in pseudo-deterministic NC

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