

(LaTeX) Abstract: 
Let $G=(V,E)$ be an unweighted undirected graph on $n$ vertices.
Let $\delta(u,v)$ denote the distance between vertices $u,v\inV$.
An algorithm is said to compute allpairs $t$approximate shortest paths/distances, for some $t\ge 1$, if for each pair of vertices
$u,v\in V$, the path/distance reported by the algorithm is not longer/greater than $t\delta(u,v)$.\\
This paper presents two randomized algorithms for computing allpairs nearly 2approximate shortest distances.
The first algorithm takes expected $O(m^{2/3}n\log n + n^2)$ time, and for any $u,v\in V$ reports distance no greater than $2\delta(u,v)+1$.
Our second algorithm requires expected $O(n^2\log^{3/2} n)$
time, and for any $u,v\in V$, reports distance bounded by $2\delta(u,v) + 3$.\\
This paper also presents the first expected $O(n^2)$ time algorithm to compute allpairs 3approximate distances. 
Keywords: 
Shortest path, distance, graph 




Download
Access Level: 
Public 
