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

DOI10.1145/3382734.3405732MaRDI QIDQ5855210zbMATH OpenOpenAlexWikidataFDO

Authors Sepehr Assadi, Gillat Kol, Rotem Oshman

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

broadcast congested cliquecommunication complexitydistributed sketchingmaximal independent setmaximal matching

Mathematics Subject Classification ID

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

Recommendations

• Distributed approximation of maximum independent set and maximum matching
• Improved distributed approximations for maximum independent set
• On the distributed complexity of computing maximal matchings
• scientific article; zbMATH DE number 1303560
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• An Improved Distributed Algorithm for Maximal Independent Set
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Distributed Computing
• Lower bounds on parallel algorithms for finding the first maximal independent set

Cited in

(2)

• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
• Rounds vs. communication tradeoffs for maximal independent sets

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

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