A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs

DOI10.1145/2888397zbMath1446.68115OpenAlexW2211624051MaRDI QIDQ4962628

Seth Pettie, Michael Elkin

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

distance oraclesdistance preservers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ New Results on Linear Size Distance Preservers ⋮ Computing Constrained Shortest-Paths at Scale