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: Goto entry point

 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:

 (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
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
Attachment Section

View attachments here: