Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 AM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
stacs05.ps