License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.54
URN: urn:nbn:de:0030-drops-79903
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7990/
Go to the corresponding LIPIcs Volume Portal

Jurdzínski, Tomasz ; Nowicki, Krzysztof

Brief Announcement: On Connectivity in the Broadcast Congested Clique

pdf-format:
LIPIcs-DISC-2017-54.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{jurdznski_et_al:LIPIcs:2017:7990,
  author =	{Tomasz Jurdz{\'i}nski and Krzysztof Nowicki},
  title =	{{Brief Announcement: On Connectivity in the Broadcast Congested Clique}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{54:1--54:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7990},
  URN =		{urn:nbn:de:0030-drops-79903},
  doi =		{10.4230/LIPIcs.DISC.2017.54},
  annote =	{Keywords: congested clique, broadcast, connected components, bandwidth}
}

Keywords: congested clique, broadcast, connected components, bandwidth
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI