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
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

URL of the conference:

http://www.siam.org/meetings/da04

URL for downloading the paper:

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
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)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
oracle.ps