A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
ACM Transactions on Algorithms · 02.09.2016 · 12 (4) · 1-31
DOI: 10.1145/2888397 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 03.08.2016. Verfasst von Michael Elkin und 1 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 40 Literaturangaben. Gefördert von: Danish National Research Foundation, NSF, Center for Massive Algorithms.
Abstract (Originalsprache)
Thorup and Zwick [2001a] proposed a landmark distance oracle with the following properties. Given an n -vertex undirected graph G = ( V , E ) and a parameter k = 1, 2, …, their oracle has size O ( kn 1 + 1/ k ), and upon a query ( u , v ) it constructs a path Π between u and v of length δ( u , v ) such that d G ( u , v ) ⩽ δ( u , v ) ⩽ (2 k − 1) d G ( u , v ). The query time of the oracle from Thorup and Zwick [2001a] is O ( k ) (in addition to the length of the returned path), and it was subsequently improved to O (1) [Wulff-Nilsen 2012; Chechik 2014]. A major drawback of the oracle of Thorup and Zwick [2001a] is that its space is Ω( n · log n ). Mendel and Naor [2006] devised an oracle with space O ( n 1 + 1/ k ) and stretch O ( k ), but their oracle can only report distance estimates and not actual paths. In this article, we devise a path-reporting distance oracle with size O ( n 1 + 1/ k ), stretch O ( k ), and query time O ( n ϵ ), for an arbitrarily small constant ϵ > 0. In particular, for k = log n , our oracle provides logarithmic stretch using linear size. Another variant of our oracle has size O ( n loglog n ), polylogarithmic stretch, and query time O (loglog n ). For unweighted graphs, we devise a distance oracle with multiplicative stretch O (1), additive stretch O (β( k )), for a function β(·), space O ( n 1 + 1/ k ), and query time O ( n ϵ ), for an arbitrarily small constant ϵ > 0. The tradeoff between multiplicative stretch and size in these oracles is far below Erdős’s girth conjecture threshold (which is stretch 2 k − 1 and size O ( n 1 + 1/ k )). Breaking the girth conjecture tradeoff is achieved by exhibiting a tradeoff of different nature between additive stretch β( k ) and size O ( n 1 + 1/ k ). A similar type of tradeoff was exhibited by a construction of (1 + ϵ, β)-spanners due to Elkin and Peleg [2001]. However, so far (1 + ϵ, β)-spanners had no counterpart in the distance oracles’ world. An important novel tool that we develop on the way to these results is a distance-preserving path-reporting oracle. We believe that this oracle is of independent interest.
Förderung
- Danish National Research Foundation
- NSF
- Center for Massive Algorithms
- Binational Science Foundation
- Lynn and William Frankel Center for Computer Science
- Israeli Academy of Science
Zitieren
APA
Elkin, M., & Pettie, S. (2016). A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. ACM Transactions on Algorithms, 12(4), 1-31. https://doi.org/10.1145/2888397
Vancouver
Elkin M, Pettie S. A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. ACM Transactions on Algorithms. 2016;12(4):1-31. doi:10.1145/2888397
BibTeX
@article{Elkin2016,
author = {Elkin, Michael and Pettie, Seth},
title = {A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs},
journal = {ACM Transactions on Algorithms},
year = {2016},
volume = {12},
number = {4},
pages = {1--31},
doi = {10.1145/2888397}
}
EUVIMED