Compact routing schemes with improved stretch

DOI10.1145/2484239.2484268zbMath1323.68029OpenAlexW2152383935MaRDI QIDQ5176080

Shiri Chechik

Publication date: 2 March 2015

Published in: Proceedings of the 2013 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2484239.2484268

zbMATH Keywords

compact routingstretch factorname-independent routing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14)

Related Items (18)

Approximate distance oracles with improved stretch for sparse graphs ⋮ Routing among convex polygonal obstacles in the plane ⋮ Routing in polygonal domains ⋮ Compact routing messages in self-healing trees ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Routing in unit disk graphs ⋮ Compact Routing in Unit Disk Graphs ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Distributed construction of purely additive spanners ⋮ Close to linear space routing schemes ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Constructing light spanners deterministically in near-linear time ⋮ Distributed Spanner Approximation ⋮ Routing in Polygonal Domains

This page was built for publication: Compact routing schemes with improved stretch