Additive spanners and distance oracles in quadratic time

DOI10.4230/LIPICS.ICALP.2017.64zbMATH Open1441.68189arXiv1704.04473MaRDI QIDQ5111395FDOQ5111395

Authors: Mathias Bæk Tejs Knudsen 

Publication date: 27 May 2020

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

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

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)

Cited In (6)

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

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)