Brief Announcement: On Connectivity in the Broadcast Congested Clique

Authors Tomasz Jurdzínski, Krzysztof Nowicki



PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.54.pdf
  • Filesize: 404 kB
  • 4 pages

Document Identifiers

Author Details

Tomasz Jurdzínski
Krzysztof Nowicki

Cite AsGet 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.
Keywords
  • congested clique
  • broadcast
  • connected components
  • bandwidth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail