Approximate Distance Oracles with Improved Query Time

Abstract

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Approximate Distance Oracles with Improved Query TimeChristian Wulff-NilsenChristian Wulff-Nilsenpp.539 - 549Chapter DOI:https://doi.org/10.1137/1.9781611973105.39PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k ≥ 2, we show that a (2k − 1)-approximate distance oracle for G of size O(kn1+1/k) and with O(log k) query time can be constructed in O(min{kmn1/k, √km + kn1+c/ √k}) time for some constant c. This improves the O(k) query time of Thorup and Zwick. Furthermore, for any 0 < ∊ ≤ 1, we give an oracle of size O(kn1+1/k) that answers ((2 + ∊)k)-approximate distance queries in O(1/∊) time. At the cost of a k-factor in size, this improves the 128k approximation achieved by the constant query time oracle of Mendel and Naor and approaches the best possible tradeoff between size and stretch, implied by a widely believed girth conjecture of Erdős. We can match the O(n1+1/k) size bound of Mendel and Naor for any constant ∊ > 0 and k = O (log n/ log log n). Previous chapter Next chapter RelatedDetails Published:2013ISBN:978-1-61197-251-1eISBN:978-1-61197-310-5 https://doi.org/10.1137/1.9781611973105Book Series Name:ProceedingsBook Code:PR143Book Pages:xix + 1915

Locations

• arXiv (Cornell University) - View - PDF