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 kspanner maintains pairwise distances up to multiplicative factor of k. It is a folklore that for every nvertex graph G, one can construct a (2k1) 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 (2k1)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 (2k1)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:140:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770927},
ISSN = {18688969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9829},
URN = {urn:nbn:de:0030drops98298},
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 