TR97-040 Authors: Dorit Dor, Shay Halperin, Uri Zwick

Publication: 19th September 1997 14:56

Downloads: 1991

Keywords:

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple

argument shows that computing all distances in G with an additive

one-sided error of at most 1 is as hard as Boolean matrix

multiplication. Building on recent work of Aingworth, Chekuri and

Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time

algorithm APASP_2 for computing all distances in G with an additive

one-sided error of at most~2. Algorithm APASP_2 is simple, easy to

implement, and faster than the fastest known matrix multiplication

algorithm. Furthermore, for every even k>2, we describe an

\tilde{O}(min{n^{2-2/(k+2)m^{2/(k+2),n^{2+2/(3k-2)}) time algorithm

APASP_k for computing all distances in G with an additive one-sided

error of at most k.

We also give an \tilde{O}(n^2) time algorithm \APASP_\infty for

producing stretch 3 estimated distances in an unweighted and

undirected graph on n vertices. No constant stretch factor was

previously achieved in \tilde{O}(n^2) time.

We say that a weighted graph F=(V,E') k-EMULATES an unweighted graph

G=(V,E) if for every u,v in V we have \delta_G(u,v) <= \delta_F(u,v)

<= \delta_G(u,v)+k. We show that every unweighted graph on n

vertices has a 2-emulator with \tilde{O}(n^{3/2}) edges and a

4-emulator with \tilde{O}(n^{4/3}) edges. These results are

asymptotically tight.

Finally, we show that any WEIGHTED undirected graph on n vertices

has a 3-spanner with \tilde{O}(n^{3/2}) edges and that such a

3-spanner can be built in \tilde{O}(mn^{1/2}) time. We also describe

an \tilde{O}(n(m^{2/3}+n)) time algorithm for estimating all

distances in a WEIGHTED undirected graph on n vertices with a stretch

factor of at most 3.

A preliminary version of this paper appeared at FOCS'96.