Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
From MaRDI portal
Publication:5171227
DOI10.1109/FOCS.2009.16zbMath1292.05243MaRDI QIDQ5171227
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (16)
Approximate distance oracles with improved stretch for sparse graphs ⋮ Thorup-Zwick emulators are universally optimal hopsets ⋮ Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs ⋮ On dynamic shortest paths problems ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Incremental single-source shortest paths in digraphs with arbitrary positive arc weights ⋮ Close to linear space routing schemes ⋮ Unnamed Item ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Fast approximate shortest paths in the congested clique ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Unnamed Item
This page was built for publication: Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
