Approximate distance oracles with improved preprocessing time

TY - GEN

T1 - Approximate distance oracles with improved preprocessing time

AU - Wulff-Nilsen, Christian

N1 - Conference code: 23

PY - 2012

Y1 - 2012

N2 - Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k ≥ 1, we show that for some universal constant c, a (2k - 1)-approximate distance oracle for G of size O(kn 1+1/k) can be constructed in O(√km + kn 1+c/√k) time and can answer queries in O(k) time. We also give an oracle which is faster for smaller k. Our results break the quadratic preprocessing time bound of Baswana and Kavitha for all k ≥ 6 and improve the O(kmn1/k) time bound of Thorup and Zwick except for very sparse graphs and small k. When m = Ω(n1+c/√k) and k = O(1), our oracle is optimal w.r.t. both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erdocombining double acute accents.

AB - Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k ≥ 1, we show that for some universal constant c, a (2k - 1)-approximate distance oracle for G of size O(kn 1+1/k) can be constructed in O(√km + kn 1+c/√k) time and can answer queries in O(k) time. We also give an oracle which is faster for smaller k. Our results break the quadratic preprocessing time bound of Baswana and Kavitha for all k ≥ 6 and improve the O(kmn1/k) time bound of Thorup and Zwick except for very sparse graphs and small k. When m = Ω(n1+c/√k) and k = O(1), our oracle is optimal w.r.t. both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erdocombining double acute accents.

M3 - Article in proceedings

SP - 202

EP - 208

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

PB - Society for Industrial and Applied Mathematics

T2 - Annual ACM-SIAM Symposium on Discrete Algorithms 2012

Y2 - 17 January 2012 through 19 January 2012

ER -