Advanced

Approximate distance oracles for graphs with dense clusters

Andersson, Mattias LU ; Gudmundsson, J and Levcopoulos, Christos LU (2004) 15th International Symposium, ISAAC 2004 In Algorithms and Computation / Lecture notes in computer science 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Algorithms and Computation / Lecture notes in computer science
volume
3341
pages
53 - 64
publisher
Springer
conference name
15th International Symposium, ISAAC 2004
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
2007-08-02 10:07:15
date last changed
2017-01-01 04:54:34
@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},
  volume       = {3341},
  year         = {2004},
}