Robust communication complexity of matching: EDCS achieves 5/6 approximation

DOI10.4230/LIPICS.ICALP.2023.14MaRDI QIDQ6638006zbMATH OpenFDO

Authors Amir Azarmehr, Soheil Behnezhad

Publication date 14 November 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2023.14

zbMATH Keywords

edge degree constrained subgraphmaximum matchingrobust communication complexity

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cited in

(2)

• Weighted matching in the random-order streaming and robust communication models
• One-way communication complexity of minimum vertex cover in general graphs

This page was built for publication: Robust communication complexity of matching: EDCS achieves 5/6 approximation

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