Advanced

Approximate distance oracles revisited

Gudmundsson, J; Levcopoulos, Christos LU ; Narasimhan, G and Smid, M (2002) 13th International Symposium, ISAAC 2002 In Algorithms and Computation, Proceedings / Lecture Notes in Computer Science 2518. p.357-368
Abstract
Let G be a geometric t-spanner in E-d with n vertices and m edges, where t is a constant. We show that G can be preprocessed in O(m log n) time, such that (1 + epsilon)-approximate shortest-path queries in G can be answered in O(1) time. The data structure uses O(n log n) space.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Algorithms and Computation, Proceedings / Lecture Notes in Computer Science
volume
2518
pages
357 - 368
publisher
Springer
conference name
13th International Symposium, ISAAC 2002
external identifiers
  • wos:000182826400032
  • scopus:84878636580
ISSN
1611-3349
0302-9743
language
English
LU publication?
yes
id
7b2840ab-fcad-4643-9206-12687648ef68 (old id 311041)
alternative location
http://www.springerlink.com/content/91wdneley60rgv1f
date added to LUP
2007-08-22 08:17:22
date last changed
2017-03-26 03:35:24
@inproceedings{7b2840ab-fcad-4643-9206-12687648ef68,
  abstract     = {Let G be a geometric t-spanner in E-d with n vertices and m edges, where t is a constant. We show that G can be preprocessed in O(m log n) time, such that (1 + epsilon)-approximate shortest-path queries in G can be answered in O(1) time. The data structure uses O(n log n) space.},
  author       = {Gudmundsson, J and Levcopoulos, Christos and Narasimhan, G and Smid, M},
  booktitle    = {Algorithms and Computation, Proceedings / Lecture Notes in Computer Science},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {357--368},
  publisher    = {Springer},
  title        = {Approximate distance oracles revisited},
  volume       = {2518},
  year         = {2002},
}