2026-07-22T22:17:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9829 2024-03-06T10:45:02Z ddc:004 open_access

Congested Clique Algorithms for Graph Spanners Parter, Merav Yogev, Eylon Distributed Graph Algorithms Spanner Congested Clique 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Merav Parter and Eylon Yogev 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.40 urn:nbn:de:0030-drops-98298 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.40 eng https://creativecommons.org/licenses/by/3.0/legalcode