On efficient distributed construction of near optimal routing schemes

DOI10.1007/s00446-017-0304-4zbMath1452.68017arXiv1602.02293OpenAlexW2259432513MaRDI QIDQ1741966

Publication date: 11 April 2018

Published in: Distributed Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Randomized algorithms (68W20) Network protocols (68M12) Distributed algorithms (68W15)

Related Items (2)

Improved weighted additive spanners ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

Cites Work

Distributed computing of efficient routing schemes in generalized chordal graphs
Efficient distributed computation of distance sketches in networks
A faster distributed protocol for constructing a minimum spanning tree
Distributed distance computation and routing with small messages
A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
Compact Routing with Minimum Stretch
Near-Optimal Scheduling of Distributed Algorithms
Fast Partial Distance Estimation and Applications
Distributed Minimum Cut Approximation
Improved routing strategies with succinct tables
An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
Approximate distance oracles
Fast Distributed Construction of Smallk-Dominating Sets and Applications
A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
Polylog-time and near-linear work approximation scheme for undirected shortest paths
Distributed Computing: A Locality-Sensitive Approach
A trade-off between space and efficiency for routing tables
Compact routing schemes with low stretch factor
Distributed Verification and Hardness of Distributed Approximation
Proximity-preserving labeling schemes
Compact and localized distributed data structures
Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
Compact routing schemes with improved stretch
Efficient distributed source detection with limited bandwidth
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
Distributed approximation algorithms for weighted shortest paths
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
On Efficient Distributed Construction of Near Optimal Routing Schemes
Routing with Improved Communication-Space Trade-Off
Fast routing table construction using small messages

This page was built for publication: On efficient distributed construction of near optimal routing schemes