Deterministic Constructions of Approximate Distance Oracles and Spanners

Thorup and Zwick showed that for any integer

k

≥ 1, it is possible to preprocess any positively weighted undirected graph

G

=(

V

,

E

), with |

E

|=

m

and |

V

|=

n

, in Õ(

kmn

$^{\rm 1/{\it k}}$

)

expected

time and construct a data structure (

a (2k

–1)-approximate distance oracle

) of size

O

(

kn

$^{\rm 1+1/{\it k}}$

) capable of returning in

O

(

k

) time an approximation

$\hat{\delta}(u,v)$

of the distance

δ

(

u

,

v

) from

u

to

v

in

G

that satisfies

$\delta(u,v) \leq \hat{\delta}(u,v) \leq (2k -1)\cdot \delta(u,v)$

, for any two vertices

u

,

v

∈

V

. They also presented a much slower Õ(

kmn

) time

deterministic

algorithm for constructing approximate distance oracle with the slightly larger size of

O

(

kn

$^{\rm 1+1/{\it k}}$

log

n

). We present here a

deterministic

Õ(

kmn

$^{\rm 1/{\it k}}$

) time algorithm for constructing oracles of size

O

(

kn

$^{\rm 1+1/{\it k}}$

). Our deterministic algorithm is slower than the randomized one by only a logarithmic factor.

Using our derandomization technique we also obtain the first deterministic

linear

time algorithm for constructing optimal spanners of weighted graphs. We do that by derandomizing the

O

(

km

) expected time algorithm of Baswana and Sen (ICALP’03) for constructing (2

k

–1)-spanners of size

O

(

kn

$^{\rm 1+1/{\it k}}$

) of weighted undirected graphs without incurring

any

asymptotic loss in the running time or in the size of the spanners produced.