Approximate distance oracles for graphs with dense clusters
Andersson, Mattias LU ; Gudmundsson, Joachim and Levcopoulos, Christos LU
(2007)
In Computational Geometry
37(3).
p.142-154
- Abstract
- Let H1=(V,E1) 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 H2=(V,E2) be the graph on V with M edges of non-negative weight. The union of the two graphs is denoted G=(V,E1 u E2). We present a data structure of size O(M^2 + nlogn) that answers (1+ε)-approximate shortest path queries in G in constant time, where ε>0 is constant.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/632105
- author
- Andersson, Mattias
LU
; Gudmundsson, Joachim
and Levcopoulos, Christos
LU
- organization
- publishing date
- 2007
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Computational Geometry
- volume
- 37
- issue
- 3
- pages
- 142 - 154
- publisher
- Elsevier
- external identifiers
-
- wos:000247424800002
- scopus:34247549396
- ISSN
- 0925-7721
- DOI
- 10.1016/j.comgeo.2004.12.011
- project
- VR 2005-4085
- language
- English
- LU publication?
- yes
- id
- 13bf10d3-b9a9-497d-bc1d-fb2f4dcc9de5 (old id 632105)
- date added to LUP
- 2016-04-04 11:17:10
- date last changed
- 2022-01-29 21:36:27
@article{13bf10d3-b9a9-497d-bc1d-fb2f4dcc9de5,
abstract = {{Let H1=(V,E1) 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 H2=(V,E2) be the graph on V with M edges of non-negative weight. The union of the two graphs is denoted G=(V,E1 u E2). We present a data structure of size O(M^2 + nlogn) that answers (1+ε)-approximate shortest path queries in G in constant time, where ε>0 is constant.}},
author = {{Andersson, Mattias and Gudmundsson, Joachim and Levcopoulos, Christos}},
issn = {{0925-7721}},
language = {{eng}},
number = {{3}},
pages = {{142--154}},
publisher = {{Elsevier}},
series = {{Computational Geometry}},
title = {{Approximate distance oracles for graphs with dense clusters}},
url = {{http://dx.doi.org/10.1016/j.comgeo.2004.12.011}},
doi = {{10.1016/j.comgeo.2004.12.011}},
volume = {{37}},
year = {{2007}},
}