Path-reporting distance oracles with linear size

DOI10.4230/LIPICS.SWAT.2024.36MaRDI QIDQ6891107zbMATH OpenFDO

Authors Ofer Neiman, Idan Shabat

Publication date 2 December 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SWAT.2024.36

zbMATH Keywords

distance oraclesgraph algorithmsshortest paths

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A linear-size logarithmic stretch path-reporting distance oracle for general graphs
• Approximate distance oracles
• Approximate distance oracles with constant query time
• Approximate distance oracles with improved bounds
• Approximate distance oracles with improved query time
• Better Distance Preservers and Additive Spanners
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Encyclopedia of Algorithms
• Engineering Route Planning Algorithms
• Having hope in hops: new spanners, preservers and lower bounds for hopsets
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• New fault tolerant subset preservers
• New pairwise spanners
• New results on linear size distance preservers
• On Pairwise Spanners
• Ramsey partitions and proximity data structures
• Shortest-path queries in static networks
• Space-efficient path-reporting approximate distance oracles
• Sparse source-wise and pair-wise distance preservers

This page was built for publication: Path-reporting distance oracles with linear size

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