MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Baswana, Surender
Goyal, Vishrut
Sen, Sandeep		dblp
dblp
dblp
Not MPG Author(s):
Goyal, Vishrut
Sen, Sandeep
Editor(s):
Diekert, Volker
Durand, Bruno		dblp
dblp
Not MPII Editor(s):
Diekert, Volker
Durand, Bruno
BibTeX cite key*:
BGS2005
Title, Booktitle
Title*:
All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time
stacs05.ps (262.36 KB)
Booktitle*:
STACS 2005 : 22nd Annual Symposium on Theoretical Aspects of Computer Science
Event, URLs
Conference URL::
Downloading URL:
http://www.mpi-inf.mpg.de/~sbaswana/Papers/stacs05.ps
Event Address*:
Stuttgart, Germany
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
8 March 2005
Event End Date:
8 March 2005
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3404
Number:
Month:
Pages:
666-679
Year*:
2005
VG Wort Pages:
ISBN/ISSN:
3-540-24998-2
Sequence Number:
DOI:
Note, Abstract, ©
(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 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.
Keywords:
Shortest path, distance, graph
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
popular
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{BGS2005,
AUTHOR = {Baswana, Surender and Goyal, Vishrut and Sen, Sandeep},
 EDITOR = {Diekert, Volker and Durand, Bruno},
 TITLE = {All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm{ polylog } n)$ time},
 BOOKTITLE = {STACS 2005 : 22nd Annual Symposium on Theoretical Aspects of Computer Science},
 PUBLISHER = {Springer},
 YEAR = {2005},
 VOLUME = {3404},
 PAGES = {666--679},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Stuttgart, Germany},
 ISBN = {3-540-24998-2},
}

Entry last modified by Surender Baswana, 08/01/2005
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Seth Pettie		Created
03/08/2005 11:05:34
Revisions
7.
6.
5.
4.
3.		Editor(s)
Surender Baswana
Surender Baswana
Surender Baswana
Christine Kiesel
Christine Kiesel		Edit Dates
08/01/2005 05:37:31 PM
08/01/2005 05:35:37 PM
08/01/2005 05:34:17 PM
26.04.2005 00:00:44
26.04.2005 00:00:32

File Attachment Icon
stacs05.ps