Approximate distance oracles with improved query time

TY - GEN

T1 - Approximate distance oracles with improved query time

AU - Wulff-Nilsen, Christian

N1 - Conference code: 24

PY - 2013

Y1 - 2013

N2 - 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 + kn 1+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 Erdo{combining double acute accent}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).

AB - 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 + kn 1+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 Erdo{combining double acute accent}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).

U2 - 10.1137/1.9781611973105.39

DO - 10.1137/1.9781611973105.39

M3 - Article in proceedings

SN - 978-1-61197-251-1

T3 - The Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings

SP - 539

EP - 549

BT - Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Khanna, Sanjeev

PB - Association for Computing Machinery

T2 - Annual ACM-SIAM Symposium on Discrete Algorithms 2013

Y2 - 6 January 2013 through 8 January 2013

ER -