Approximation of distances and shortest paths in the broadcast congest clique

DOI10.4230/LIPICS.OPODIS.2015.6MaRDI QIDQ5363797zbMATH OpenFDO

Authors Stephan Holzer, Nathan Pinsker

Publication date 29 September 2017

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

zbMATH Keywords

distributed computingapproximation algorithmsdistributed algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• Fast approximate shortest paths in the congested clique
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Reachability and shortest paths in the broadcast CONGEST model
• Distributed approximation algorithms for weighted shortest paths

Cited in

(15)

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Derandomizing local distributed algorithms under bandwidth restrictions
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Large-scale distributed algorithms for facility location with outliers
• Distributed distance computation and routing with small messages
• Exponentially Faster Shortest Paths in the Congested Clique
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Fast partial distance estimation and applications
• Connectivity and minimum cut approximation in the broadcast congested clique
• Lessons from the congested clique applied to MapReduce
• The impact of locality in the broadcast congested clique model
• Reachability and shortest paths in the broadcast CONGEST model
• Fast approximate shortest paths in the congested clique
• Improved hardness of approximation of diameter in the CONGEST model
• Quadratic and near-quadratic lower bounds for the CONGEST model

This page was built for publication: Approximation of distances and shortest paths in the broadcast congest clique

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