All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing

DOI10.4230/LIPICS.ICALP.2016.55MaRDI QIDQ4598194zbMATH OpenOpenAlexFDO

Authors C. Sommer

Publication date 19 December 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.ICALP.2016.55

zbMATH Keywords

approximate shortest pathsdata structuresdistance labelsdistance oraclesgraph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Faster algorithms for all-pairs approximate shortest paths in undirected graphs
• Dynamic approximate all-pairs shortest paths in undirected graphs
• An almost 2-approximation for all-pairs of shortest paths in subquadratic time
• All-pairs shortest paths with a sublinear additive error
• All-Pairs Shortest Paths with a Sublinear Additive Error
• All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Efficient parameterized algorithms for computing all-pairs shortest paths
• STACS 2005

Cited in

(8)

• Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
• All-pairs shortest paths with a sublinear additive error
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Approximate distance oracles with improved preprocessing time
• New algorithms for all pairs approximate shortest paths
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• On the space usage of approximate distance oracles with sub-2 stretch
• New tradeoffs for decremental approximate all-pairs shortest paths

This page was built for publication: All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing

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