Approximate distance oracles revisited
Gudmundsson, J ; Levcopoulos, Christos LU
; Narasimhan, G
and Smid, M
(2002)
13th International Symposium, ISAAC 2002
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:
https://lup.lub.lu.se/record/311041
- author
- Gudmundsson, J
; Levcopoulos, Christos
LU
; Narasimhan, G
and Smid, M
- organization
- publishing date
- 2002
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Algorithms and Computation, Proceedings / Lecture Notes in Computer Science
- volume
- 2518
- pages
- 357 - 368
- publisher
- Springer
- conference name
- 13th International Symposium, ISAAC 2002
- conference location
- Vancouver, BC, Canada
- conference dates
- 2002-11-21 - 2002-11-23
- external identifiers
-
- wos:000182826400032
- scopus:84878636580
- ISSN
- 0302-9743
- 1611-3349
- 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
- 2016-04-01 12:07:49
- date last changed
- 2024-01-08 09:25:47
@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 = {{0302-9743}},
language = {{eng}},
pages = {{357--368}},
publisher = {{Springer}},
title = {{Approximate distance oracles revisited}},
url = {{http://www.springerlink.com/content/91wdneley60rgv1f}},
volume = {{2518}},
year = {{2002}},
}