Connectivity Lower Bounds in Broadcast Congested Clique

DOI10.1145/3293611.3331569MaRDI QIDQ5145216zbMATH OpenOpenAlexFDO

Authors Shreyas Pai, Sriram Pemmaraju

Publication date 20 January 2021

Published in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.09016, https://drops.dagstuhl.de/opus/volltexte/2020/13273/

zbMATH Keywords

broadcast congested cliquecommunication complexityconnectivityinformation theorylower boundsset partition

Mathematics Subject Classification ID

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

Recommendations

• Toward optimal bounds in the congested clique, graph connectivity and MST
• Brief announcement: Deterministic graph connectivity in the broadcast congested clique
• Connectivity and minimum cut approximation in the broadcast congested clique
• On the power of the congested clique model
• On range and edge capacity in the congested clique

Cited in

(5)

• Connectivity and minimum cut approximation in the broadcast congested clique
• The role of randomness in the broadcast congested clique model
• Toward optimal bounds in the congested clique, graph connectivity and MST
• Broadcast Congested Clique
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE

This page was built for publication: Connectivity Lower Bounds in Broadcast Congested Clique

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