All reports by Author Shay Halperin:

__
TR97-040
| 17th September 1997
__

Dorit Dor, Shay Halperin, Uri Zwick#### All Pairs Almost Shortest Paths

Dorit Dor, Shay Halperin, Uri Zwick

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

more >>>