Follow us on
Distance Oracles for Time-Dependent Networks
Submitted by gkortsilas on Sat, 2013-08-31 19:41
Publication Date:
July, 2013
Abstract:
Abstract. We present the rst approximate distance oracles for sparse directed networks
with time-dependent arc-travel-times determined by continuous, piecewise linear, positive
functions possessing the FIFO property. Our approach precomputes, in subquadratic time
and space, (1+ε) approximate distance summaries from selected vertices to all other vertices
in the network, and provides two sublinear time query algorithms that deliver constant
and (1+σ) approximate shortest-travel-times, respectively, for arbitrary origin-destination
pairs in the network. More specically, our contributions are threefold: (i) we present a
one-to-all polynomial-time algorithm for computing (1 + ε) approximations of the shortest-
travel-travel time functions from a specic origin to all other vertices in the network, using
space per approximate travel-time function that is asymptotically optimal and independent
of the network size; (ii) we give a constant-approximation query algorithm of sublinear time
complexity for arbitrary origin-destination pairs based on distance summaries precomputed
from a subset of vertices (landmarks) to all other vertices using the one-to-all algorithm; (iii)
we give a query algorithm that recursively uses the precomputed distance summaries and
the constant-approximation algorithm, in order to achieve a (1 + σ)-stretch factor, for any
File:
Work Packages:
