Congested clique algorithms for graph spanners

DOI10.4230/LIPICS.DISC.2018.40MaRDI QIDQ5090933zbMATH OpenOpenAlexFDO

Authors Eylon Yogev, M. Parter

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1805.05404

zbMATH Keywords

spannerdistributed graph algorithmscongested clique

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

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: (1) A randomized construction of a $(2k-1)$-spanner with $widetildeO(n^{1+1/k})$ edges in $O(logk)$ rounds. The previous best algorithm runs in $O(k)$ rounds. (2) A deterministic construction of a $(2k-1)$-spanner with $widetildeO(n^{1+1/k})$ edges in $O(logk+(loglogn{)}^3)$ rounds. The previous best algorithm runs in $O(klogn)$ rounds. This improvement is achieved by a new derandomization theorem for hitting sets which might be of independent interest. (3) A deterministic construction of a $O(k)$-spanner with $O(kcdot{n}^{1+1/k})$ edges in $O(logk)$ rounds.

Recommendations

• Improved deterministic distributed construction of spanners
• On the locality of distributed sparse spanner construction
• Fast deterministic distributed algorithms for sparse spanners
• Simple distributed spanners in dense congest networks
• Fast Deterministic Distributed Algorithms for Sparse Spanners

Cites work

• An Improved Distributed Algorithm for Maximal Independent Set
• An Optimal Synchronizer for the Hypercube
• Automata, Languages and Programming
• Balls and bins: smaller hash families and faster evaluation
• Derandomizing local distributed algorithms under bandwidth restrictions
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• Distributed Computing: A Locality-Sensitive Approach
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Fast deterministic distributed algorithms for sparse spanners
• Graph spanners
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Lessons from the congested clique applied to MapReduce
• Local Computation of Nearly Additive Spanners
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• On the locality of distributed sparse spanner construction
• Optimal deterministic routing and sorting on the congested clique
• Sublinear fully distributed partition with applications
• Transitive-closure spanners

Cited in

(8)

• Simple distributed spanners in dense congest networks
• Improved deterministic distributed construction of spanners
• Lessons from the Congested Clique Applied to MapReduce
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Fast approximate shortest paths in the congested clique
• Congested Clique Algorithms for the Minimum Cut Problem
• The sparsest additive spanner via multiple weighted BFS trees
• Toward optimal bounds in the congested clique, graph connectivity and MST

This page was built for publication: Congested clique algorithms for graph spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090933)