2026-07-24T00:57:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7392 2024-03-06T10:40:24Z ddc:004 open_access

Additive Spanners and Distance Oracles in Quadratic Time Knudsen, Mathias Bæk Tejs graph algorithms data structures additive spanners distance oracles Let G be an unweighted, undirected graph. An additive k-spanner of G is a subgraph H that approximates all distances between pairs of nodes up to an additive error of +k, that is, it satisfies d_H(u,v) <= d_G(u,v)+k for all nodes u,v, where d is the shortest path distance. We give a deterministic algorithm that constructs an additive O(1)-spanner with O(n^(4/3)) edges in O(n^2) time. This should be compared with the randomized Monte Carlo algorithm by Woodruff [ICALP 2010] giving an additive 6-spanner with O(n^(4/3)log^3 n) edges in expected time O(n^2 log^2 n). An (alpha,beta)-approximate distance oracle for G is a data structure that supports the following distance queries between pairs of nodes in G. Given two nodes u, v it can in constant time compute a distance estimate d' that satisfies d <= d' <= alpha d + beta where d is the distance between u and v in G. Sommer [ICALP 2016] gave a randomized Monte Carlo (2,1)-distance oracle of size O(n^(5/3) polylog n) in expected time O(n^2 polylog n). As an application of the additive O(1)-spanner we improve the construction by Sommer [ICALP 2016] and give a Las Vegas (2,1)-distance oracle of size O(n^(5/3)) in time O(n^2). This also implies an algorithm that in O(n^2) time gives approximate distance for all pairs of nodes in G improving on the O(n^2 log n) algorithm by Baswana and Kavitha [SICOMP 2010]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mathias Bæk Tejs Knudsen 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.64 urn:nbn:de:0030-drops-73924 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.64 eng https://creativecommons.org/licenses/by/3.0/legalcode