Fast routing table construction using small messages

DOI10.1145/2488608.2488656zbMath1293.68058OpenAlexW2112702616MaRDI QIDQ5495808

Christoph Lenzen, Boaz Patt-Shamir

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

routingapproximate shortest pathssmall messages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Single-source shortest paths in the CONGEST model with improved bounds ⋮ Distributed distance computation and routing with small messages ⋮ Routing schemes for hybrid communication networks ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Fast approximate shortest paths in the congested clique ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots