Approximate distance oracles for graphs with dense clusters
Andersson, Mattias LU ; Gudmundsson, J and Levcopoulos, Christos LU
(2004)
15th International Symposium, ISAAC 2004
3341.
p.53-64
- Abstract
- Let H-1 = (V, F-1) be a collection of N pairwise vertex disjoint O(1)-spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let H-2 = (V, F-2) be a graph on V with M edges of non-negative weight. The union of the two graphs is denoted G = (V, F-1 boolean OR F-2). We present a data structure of size O(M-2 + V log V) that answers (1 + epsilon)-approximate shortest path queries in G in constant time, where epsilon > 0 is constant.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/254705
- author
- Andersson, Mattias
LU
; Gudmundsson, J
and Levcopoulos, Christos
LU
- organization
- publishing date
- 2004
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Algorithms and Computation / Lecture notes in computer science
- volume
- 3341
- pages
- 53 - 64
- publisher
- Springer
- conference name
- 15th International Symposium, ISAAC 2004
- conference location
- Hong Kong, China
- conference dates
- 2004-12-20 - 2004-12-22
- external identifiers
-
- wos:000226690300005
- scopus:35048902473
- ISSN
- 1611-3349
- 0302-9743
- DOI
- 10.1007/978-3-540-30551-4_7
- project
- VR 2002-4049
- language
- English
- LU publication?
- yes
- id
- d49a5b71-6a37-4c94-b7a4-5588830a5082 (old id 254705)
- date added to LUP
- 2016-04-01 12:10:29
- date last changed
- 2024-01-08 11:03:00
@inproceedings{d49a5b71-6a37-4c94-b7a4-5588830a5082,
abstract = {{Let H-1 = (V, F-1) be a collection of N pairwise vertex disjoint O(1)-spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let H-2 = (V, F-2) be a graph on V with M edges of non-negative weight. The union of the two graphs is denoted G = (V, F-1 boolean OR F-2). We present a data structure of size O(M-2 + V log V) that answers (1 + epsilon)-approximate shortest path queries in G in constant time, where epsilon > 0 is constant.}},
author = {{Andersson, Mattias and Gudmundsson, J and Levcopoulos, Christos}},
booktitle = {{Algorithms and Computation / Lecture notes in computer science}},
issn = {{1611-3349}},
language = {{eng}},
pages = {{53--64}},
publisher = {{Springer}},
title = {{Approximate distance oracles for graphs with dense clusters}},
url = {{http://dx.doi.org/10.1007/978-3-540-30551-4_7}},
doi = {{10.1007/978-3-540-30551-4_7}},
volume = {{3341}},
year = {{2004}},
}