Knudsen, Mathias Bæk Tejs
Additive Spanners and Distance Oracles in Quadratic Time
Abstract
Let G be an unweighted, undirected graph. An additive kspanner 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 6spanner 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].
BibTeX  Entry
@InProceedings{knudsen:LIPIcs:2017:7392,
author = {Mathias Bæk Tejs Knudsen},
title = {{Additive Spanners and Distance Oracles in Quadratic Time}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {64:164:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7392},
URN = {urn:nbn:de:0030drops73924},
doi = {10.4230/LIPIcs.ICALP.2017.64},
annote = {Keywords: graph algorithms, data structures, additive spanners, distance oracles}
}
07.07.2017
Keywords: 

graph algorithms, data structures, additive spanners, distance oracles 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 