Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets

DOI10.1145/3382734.3405732OpenAlexW3046669889MaRDI QIDQ5855210

Gillat Kol, Rotem Oshman, Sepehr Assadi

Publication date: 15 March 2021

Published in: Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3382734.3405732

zbMATH Keywords

communication complexitymaximal matchingmaximal independent setbroadcast congested cliquedistributed sketching

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

This page was built for publication: Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets