Fast routing table construction using small messages (extended abstract)

DOI10.1145/2488608.2488656MaRDI QIDQ5495808zbMATH OpenOpenAlexFDO

Authors Christoph Lenzen, Boaz Patt-Shamir

Publication date 7 August 2014

Published in Proceedings of the forty-eighth 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

approximate shortest pathsroutingsmall messages

Mathematics Subject Classification ID

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

Recommendations

• On efficient distributed construction of near optimal routing schemes (extended abstract)
• On efficient distributed construction of near optimal routing schemes
• Distributed approximation algorithms for weighted shortest paths
• Fast partial distance estimation and applications
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

Cited in

(17)

• On efficient distributed construction of near optimal routing schemes
• Fast approximate shortest paths in the congested clique
• Single-source shortest paths in the CONGEST model with improved bounds
• Distributed distance computation and routing with small messages
• A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
• Fast partial distance estimation and applications
• 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
• Distributed MST and broadcast with fewer messages, and faster gossiping
• On efficient distributed construction of near optimal routing schemes (extended abstract)
• Finding a small vertex cut on distributed networks
• Distributed distance approximation
• Tight bounds on the message complexity of distributed tree verification
• A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP
• Polylogarithmic time algorithms for shortest path forests in programmable matter
• Efficient distributed computation of distance sketches in networks

This page was built for publication: Fast routing table construction using small messages (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495808)