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 -