de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44080

Baswana,  Surender
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45456

Sen,  Sandeep
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Baswana, S., Goyal, V., & Sen, S. (2005). All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time. In STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science (pp. 666-679). Berlin, Germany: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2592-9
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 all-pairs $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 all-pairs nearly 2-approximate 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 all-pairs 3-approximate distances.