Approximate distance oracles with improved stretch for sparse graphs

DOI10.1007/978-3-030-89543-3_8OpenAlexW3208285667MaRDI QIDQ5972260

Roei Tov, Liam Roditty

Publication date: 30 March 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-89543-3_8

zbMATH Keywords

graph algorithmsapproximate shortest pathsapproximate distance oracles

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Approximate distance oracles with improved stretch for sparse graphs

Uses Software

• GitHub

Cites Work

• New Routing Techniques and their Applications
• Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
• Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
• The Power of Dynamic Distance Oracles
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Approximate distance oracles
• Compact Routing in Power-Law Graphs
• Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
• Compact routing schemes with improved stretch
• Distance Oracles beyond the Thorup--Zwick Bound
• Approximate Distance Oracles with Improved Query Time
• Close to linear space routing schemes
• Approximate distance oracles with improved stretch for sparse graphs

This page was built for publication: Approximate distance oracles with improved stretch for sparse graphs