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.2018.40
URN: urn:nbn:de:0030-drops-98298
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9829/
Go to the corresponding LIPIcs Volume Portal

Parter, Merav ; Yogev, Eylon

Congested Clique Algorithms for Graph Spanners

pdf-format:
LIPIcs-DISC-2018-40.pdf (0.8 MB)

Abstract

Graph spanners are sparse subgraphs that faithfully preserve the distances in the original graph up to small stretch. Spanner have been studied extensively as they have a wide range of applications ranging from distance oracles, labeling schemes and routing to solving linear systems and spectral sparsification. A k-spanner maintains pairwise distances up to multiplicative factor of k. It is a folklore that for every n-vertex graph G, one can construct a (2k-1) spanner with O(n^{1+1/k}) edges. In a distributed setting, such spanners can be constructed in the standard CONGEST model using O(k^2) rounds, when randomization is allowed.
In this work, we consider spanner constructions in the congested clique model, and show:
- a randomized construction of a (2k-1)-spanner with O~(n^{1+1/k}) edges in O(log k) rounds. The previous best algorithm runs in O(k) rounds;
- a deterministic construction of a (2k-1)-spanner with O~(n^{1+1/k}) edges in O(log k +(log log n)^3) rounds. The previous best algorithm runs in O(k log n) rounds. This improvement is achieved by a new derandomization theorem for hitting sets which might be of independent interest;
- a deterministic construction of a O(k)-spanner with O(k * n^{1+1/k}) edges in O(log k) rounds.

BibTeX - Entry

@InProceedings{parter_et_al:LIPIcs:2018:9829,
  author =	{Merav Parter and Eylon Yogev},
  title =	{{Congested Clique Algorithms for Graph Spanners}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9829},
  URN =		{urn:nbn:de:0030-drops-98298},
  doi =		{10.4230/LIPIcs.DISC.2018.40},
  annote =	{Keywords: Distributed Graph Algorithms, Spanner, Congested Clique}
}

Keywords: Distributed Graph Algorithms, Spanner, Congested Clique
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

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