Approximate distance oracles for graphs with dense clusters
(2004) 15th International Symposium, ISAAC 2004 In Algorithms and Computation / Lecture notes in computer science 3341. p.5364 Abstract
 Let H1 = (V, F1) 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, F2) be a graph on V with M edges of nonnegative weight. The union of the two graphs is denoted G = (V, F1 boolean OR F2). We present a data structure of size O(M2 + 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:
http://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
 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
 16113349
 03029743
 DOI
 10.1007/9783540305514_7
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 d49a5b716a374c94b7a45588830a5082 (old id 254705)
 date added to LUP
 20070802 10:07:15
 date last changed
 20170101 04:54:34
@inproceedings{d49a5b716a374c94b7a45588830a5082, abstract = {Let H1 = (V, F1) 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, F2) be a graph on V with M edges of nonnegative weight. The union of the two graphs is denoted G = (V, F1 boolean OR F2). We present a data structure of size O(M2 + 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 = {16113349}, language = {eng}, pages = {5364}, publisher = {Springer}, title = {Approximate distance oracles for graphs with dense clusters}, url = {http://dx.doi.org/10.1007/9783540305514_7}, volume = {3341}, year = {2004}, }