MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Baswana, Surender
Sen, Sandeep		dblp
dblp
Not MPG Author(s):
Sen, Sandeep
Editor(s):
BibTeX cite key*:
BS2004
Title, Booktitle
Title*:
Approximate distance oracle for unweighted graphs in Expected O(n²) time
oracle.ps (269.35 KB)
Booktitle*:
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da04
Downloading URL:
http://www.mpi-sb.mpg.de/~sbaswana/Papers/oracle.ps
Event Address*:
New Orleans, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
11 January 2004
Event End Date:
13 January 2004
Publisher
Name*:
ACM
URL:
http://www.siam.org
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
271-280
Year*:
2004
VG Wort Pages:
ISBN/ISSN:
0-89871-XXX-X
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Let $G=(V,E)$ be an undirected graph on $n$ vertices, and let $\delta(u,v)$ denote the distance in $G$ between two vertices $u$ and $v$. Thorup and Zwick showed that for any +ve integer $t$, the
graph $G$ can be preprocessed to build a data-structure that can efficiently report $t$-approximate distance between any pair of vertices. That is, for any $u,v\in V$, the distance reported $\hat{\delta}(u,v)$ satisfies
\[
\delta(u,v) \le \hat{\delta}(u,v) \le t \delta(u,v)
\]
The remarkable feature of this data-structure is that, for $t>2$,
it occupies sub-quadratic space, i.e., it does not store all-pairs distances information explicitly, and still can answer
any $t$-approximate distance query in constant time. They named the data-structure "oracle" because of this feature. Furthermore, the tradeoff between stretch $t$ and the size of the data-structure is essentially optimal.
In this paper we show that we can actually construct approximate distance oracles in expected $O(n^2)$ time if the graph is unweighted. One of the new ideas used in the improved algorithm also leads to the first expected linear time algorithm for computing an optimal size $(2,1)$-spanner of an unweighted graph. A $(2,1)$-spanner of a graph $G=(V,E)$ is a subgraph $G=(V,E_S), E_S\subset E$, such that for any two vertices
$u$ and $v$ in the graph, their distance in the subgraph is at most $2\delta(u,v)+1$.
Keywords:
Distance, Shortest Path, Graph Algorithm
Personal Comments:
The paper is a revised version of the paper that appeared in the conference SODA 2004.
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{BS2004,
AUTHOR = {Baswana, Surender and Sen, Sandeep},
 TITLE = {Approximate distance oracle for unweighted graphs in Expected O(n²) time},
 BOOKTITLE = {Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)},
 PUBLISHER = {ACM},
 YEAR = {2004},
 PAGES = {271--280},
 ADDRESS = {New Orleans, USA},
 ISBN = {0-89871-XXX-X},
}

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)
Surender Baswana		Created
05/04/2004 05:48:43 PM
Revisions
12.
11.
10.
9.
8.		Editor(s)
Surender Baswana
Surender Baswana
Surender Baswana
Uwe Brahm
Uwe Brahm		Edit Dates
08/01/2005 05:14:19 PM
08/01/2005 05:11:38 PM
08/01/2005 05:10:28 PM
06/28/2005 04:56:40 PM
06/28/2005 04:55:32 PM

File Attachment Icon
oracle.ps