LIPIcs.DISC.2017.54.pdf
- Filesize: 404 kB
- 4 pages
Document
Brief Announcement: On Connectivity in the Broadcast Congested Clique
Authors
-
Part of:
Volume:
31st International Symposium on Distributed Computing (DISC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-10-12
Cite As Get BibTex
Tomasz Jurdzínski and Krzysztof Nowicki. Brief Announcement: On Connectivity in the Broadcast Congested Clique. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 54:1-54:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.54
Abstract
Recently, very fast deterministic and randomized algorithms have been obtained for connectivity and minimum spanning tree in the unicast congested clique. In contrast, no solution faster than a simple parallel implementation of the Boruvka's algorithm has been known for both problems in the broadcast congested clique. In this announcement, we present the first sub-logarithmic deterministic algorithm for connected components in the broadcast congested clique.
Subject Classification
Keywords
- congested clique
- broadcast
- connected components
- bandwidth
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of SODA 2012, pages 459-467, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095156.
- Mohsen Ghaffari and Merav Parter. MST in log-star rounds of congested clique. In Proceedings of PODC 2016, pages 19-28, 2016. URL: http://dx.doi.org/10.1145/2933057.2933103.
- James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. Toward optimal bounds in the congested clique: Graph connectivity and MST. In Proceedings of PODC 2015, pages 91-100, 2015. URL: http://dx.doi.org/10.1145/2767386.2767434.
- Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput., 35(1):120-131, 2005. URL: http://dx.doi.org/10.1137/S0097539704441848.
- Pedro Montealegre and Ioan Todinca. Brief announcement: Deterministic graph connectivity in the broadcast congested clique. In Proceedings of PODC 2016, pages 245-247, 2016. URL: http://dx.doi.org/10.1145/2933057.2933066.