Baswana, Surender ; Goyal, Vishrut ; Sen, Sandeep
(2009)
*All-pairs nearly 2-approximate shortest paths in O(n ^{2}polylog n) time*
Theoretical Computer Science, 410
(1).
pp. 84-93.
ISSN 0304-3975

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1016/j.tcs.2008.10.018

## Abstract

Let G=(V,E) be an unweighted undirected graph on |V|=n vertices and |E|=m edges. Let δ(u,v) denote the distance between vertices u,v∈V. An algorithm is said to compute all-pairs t-approximate shortest-paths/distances, for some t≥1, if for each pair of vertices u,v∈V, the path/distance reported by the algorithm is not longer/greater than t·δ(u,v). This paper presents two extremely simple randomized algorithms for computing all-pairs nearly 2-approximate distances. The first algorithm requires an expected O(m^{2/3}nlogn+n^{2}) time, and for any u,v∈V reports a distance no greater than 2δ(u,v)+1. Our second algorithm requires an expected O(n^{2}log^{3/2}) time, and for any u,v∈V reports a distance bounded by 2δ(u,v)+3. This paper also presents the first expected O(n^{2}) time algorithm to compute all-pairs 3-approximate distances.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Elsevier Science. |

Keywords: | Shortest Path; Distance; Spanner |

ID Code: | 53445 |

Deposited On: | 08 Aug 2011 12:14 |

Last Modified: | 08 Aug 2011 12:14 |

Repository Staff Only: item control page