2026-08-08T04:16:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11820 2024-03-06T10:48:51Z ddc:004 open_access

Sparse Hopsets in Congested Clique Nazari, Yasamin Hopsets Congested Clique Shortest Paths Massively Parallel Computation We give the first Congested Clique algorithm that computes a sparse hopset with polylogarithmic hopbound in polylogarithmic time. Given a graph G=(V,E), a (β,ε)-hopset H with "hopbound" β, is a set of edges added to G such that for any pair of nodes u and v in G there is a path with at most β hops in G ∪ H with length within (1+ε) of the shortest path between u and v in G. Our hopsets are significantly sparser than the recent construction of [Censor-Hillel et al., 2019], that constructs a hopset of size Õ (n^{3/2}), but with a smaller polylogarithmic hopbound. On the other hand, the previously known construction of sparse hopsets with polylogarithmic hopbound in the Congested Clique model, proposed by [Elkin and Neiman, 2018; Elkin and Neiman, 2019; Elkin and Neiman, 2019], all require polynomial rounds. One tool that we use is an efficient algorithm that constructs an l-limited neighborhood cover, that may be of independent interest. Finally, as a side result, we also give a hopset construction in a variant of the low-memory Massively Parallel Computation model, with improved running time over existing algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yasamin Nazari 2020 Is Part Of LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2019.34 urn:nbn:de:0030-drops-118207 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.34 eng https://creativecommons.org/licenses/by/3.0/legalcode