Congested clique algorithms for graph spanners

DOI10.4230/LIPICS.DISC.2018.40zbMATH Open1497.68569arXiv1805.05404OpenAlexW2963005538MaRDI QIDQ5090933FDOQ5090933

Authors: Eylon Yogev, M. Parter 

Publication date: 21 July 2022

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.

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

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

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)

Cites Work

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

Cited In (8)

• Congested Clique Algorithms for the Minimum Cut Problem
• Improved deterministic distributed construction of spanners
• Lessons from the Congested Clique Applied to MapReduce
• The sparsest additive spanner via multiple weighted BFS trees
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Fast approximate shortest paths in the congested clique
• Algebraic methods in the congested clique
• 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)