Efficient distributed computation of distance sketches in networks
From MaRDI portal
Publication:748116
DOI10.1007/S00446-015-0246-7zbMath1342.68349arXiv1112.1210OpenAlexW634346220MaRDI QIDQ748116
Atish Das Sarma, Michael Dinitz, Gopal Pandurangan
Publication date: 20 October 2015
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1112.1210
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Distributed algorithms (68W15)
Related Items (4)
Distributed distance computation and routing with small messages ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ On efficient distributed construction of near optimal routing schemes ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple efficient load-balancing algorithms for peer-to-peer systems
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Labeling schemes for tree representation
- A fast distributed approximation algorithm for minimum spanning trees
- Collisions Among Random Walks on a Graph
- The small-world phenomenon
- Triangulation and embedding using small sets of beacons
- Approximate distance oracles
- Distributed Computing: A Locality-Sensitive Approach
- Labeling Schemes for Flow and Connectivity
- Distance labeling in graphs
- Spatial gossip and resource location protocols
- Distance estimation and object location via rings of neighbors
- Towards fast decentralized construction of locality-aware overlay networks
- Point-to-Point Shortest Path Algorithms with Preprocessing
- Spanners with Slack
- Automata, Languages and Programming
- Efficient distributed approximation algorithms via probabilistic tree embeddings
This page was built for publication: Efficient distributed computation of distance sketches in networks
