Additive spanners and distance oracles in quadratic time

DOI10.4230/LIPICS.ICALP.2017.64MaRDI QIDQ5111395zbMATHFDO

Authors Mathias Bæk Tejs Knudsen

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1704.04473

zbMATH Keywords

data structuresgraph algorithmsdistance oraclesadditive spanners

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6469155
• Additive spanners in nearly quadratic time
• Automata, Languages and Programming
• Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error

Cited in

(6)

• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• Automata, Languages and Programming
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Graph spanners: a tutorial review
• Additive spanners in nearly quadratic time
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

This page was built for publication: Additive spanners and distance oracles in quadratic time

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