Distributed distance computation and routing with small messages
From MaRDI portal
Publication:2422769
DOI10.1007/s00446-018-0326-6zbMath1451.68049OpenAlexW2793130010MaRDI QIDQ2422769
Boaz Patt-Shamir, Christoph Lenzen, David Peleg
Publication date: 20 June 2019
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-018-0326-6
compact routingsource detectionCONGEST modelall-pairs shortest pathssingle-souce shortest pathsskeleton spanner
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14) Distributed algorithms (68W15) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items
Low-congestion shortcuts without embedding ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ On efficient distributed construction of near optimal routing schemes ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient distributed computation of distance sketches in networks
- A fully dynamic approximation scheme for shortest paths in planar graphs
- Near-linear lower bounds for distributed distance computations, even in sparse networks
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Fast Partial Distance Estimation and Applications
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- Optimal distributed all pairs shortest paths and applications
- On the locality of distributed sparse spanner construction
- Improved distributed steiner forest construction
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- Distributed Algorithms for Network Diameter and Girth
- Improved routing strategies with succinct tables
- Labelling and Implicit Routing in Networks
- On a routing problem
- Distributed network protocols
- Approximate distance oracles
- Graph spanners
- Routing with Polynomial Communication-Space Trade-Off
- An ‘All Pairs Shortest Paths’ Distributed Algorithm Using 2n2Messages
- Distributed Computing: A Locality-Sensitive Approach
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Compact and localized distributed data structures
- Efficient distributed source detection with limited bandwidth
- Distributed approximation algorithms for weighted shortest paths
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- On Efficient Distributed Construction of Near Optimal Routing Schemes
- Distributed verification and hardness of distributed approximation
- Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
- Fast routing table construction using small messages
- Maintaining shortest paths under deletions in weighted directed graphs
- Automata, Languages and Programming
