EUVIMEDEUVIMED entdecken
Crossref

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs

Michael Elkin, Seth Pettie

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →