Congested Clique Algorithms for Graph Spanners

DOI10.4230/LIPIcs.DISC.2018.40zbMath1497.68569arXiv1805.05404OpenAlexW2963005538MaRDI QIDQ5090933

Eylon Yogev, Merav 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)

Related Items (3)

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

Cites Work

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

This page was built for publication: Congested Clique Algorithms for Graph Spanners