Towards a unified theory of sparsification for matching problems

DOI10.4230/OASICS.SOSA.2019.11zbMATH Open1547.68535MaRDI QIDQ6593566

Aaron Bernstein, Sepehr Assadi

Publication date: 26 August 2024

zbMATH Keywords

maximum matchingone-way communication complexitystochastic matchingmatching sparsifiersfault-tolerant matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Communication complexity, information complexity (68Q11)

Related Items (1)

Improved bounds for matching in random-order streams

This page was built for publication: Towards a unified theory of sparsification for matching problems

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