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 pu, vq ď d G pu, vq`k for all nodes u, v, where d is the shortest path distance. We give a deterministic algorithm that constructs an additive Op1q-spanner with O`n 4{3˘e dges in O`n 2˘t ime. 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 pα, βq-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 estimated that satisfies d ďd ď αd`β where d is the distance between u and v in G. Sommer [ICALP 2016] gave a randomized Monte Carlo p2, 1q-distance oracle of size O`n 5{3 poly log nȋ n expected time O`n 2 poly log n˘. As an application of the additive Op1q-spanner we improve the construction by Sommer [ICALP 2016] and give a Las Vegas p2, 1q-distance oracle of size O`n 5{3˘i n time O`n 2˘. This also implies an algorithm that in O`n 2˘g ives approximate distance for all pairs of nodes in G improving on the O`n 2 log n˘algorithm by Baswana and Kavitha [SICOMP 2010].
The construction time was recently improved to O(n 2 ) by Knudsen REF .
Additive Spanners and Distance Oracles in Quadratic Time
ArXiv
ArXiv
Computer Science Mathematics