TY - GEN

T1 - Distance oracles for stretch less than 2

AU - Agarwal, Rachit

AU - Godfrey, P. Brighten

PY - 2013

Y1 - 2013

N2 - We present distance oracles for weighted undirected graphs that return distances of stretch less than 2. For the realistic case of sparse graphs, our distance oracles exhibit a smooth three-way trade-off between space, stretch and query time - a phenomenon that does not occur in dense graphs. In particular, for any positive integer t and for any 1 ≤ α ≤ n, our distance oracle is of size O(m + n2/α) and returns distances of stretch at most (1 + 2/t+1) in time O((αμ)t), where μ = 2m/n is the average degree of the graph. The query time can be further reduced to O((α + μ)t) at the expense of a small additive stretch.

AB - We present distance oracles for weighted undirected graphs that return distances of stretch less than 2. For the realistic case of sparse graphs, our distance oracles exhibit a smooth three-way trade-off between space, stretch and query time - a phenomenon that does not occur in dense graphs. In particular, for any positive integer t and for any 1 ≤ α ≤ n, our distance oracle is of size O(m + n2/α) and returns distances of stretch at most (1 + 2/t+1) in time O((αμ)t), where μ = 2m/n is the average degree of the graph. The query time can be further reduced to O((α + μ)t) at the expense of a small additive stretch.

UR - http://www.scopus.com/inward/record.url?scp=84876051419&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84876051419&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973105.38

DO - 10.1137/1.9781611973105.38

M3 - Conference contribution

AN - SCOPUS:84876051419

SN - 9781611972511

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 526

EP - 538

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

PB - Association for Computing Machinery

T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

Y2 - 6 January 2013 through 8 January 2013

ER -