Advanced

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:
author
organization
publishing date
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
2007-11-28 12:21:43
date last changed
2016-10-13 04:44:55
@misc{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    = {ARRAY(0x9e7cd10)},
  series       = {Computational Geometry},
  title        = {Approximate distance oracles for graphs with dense clusters},
  url          = {http://dx.doi.org/10.1016/j.comgeo.2004.12.011},
  volume       = {37},
  year         = {2007},
}