Du är här

Approximate distance oracles for graphs with dense clusters

Publiceringsår: 2007
Språk: Engelska
Sidor: 142-154
Publikation/Tidskrift/Serie: Computational Geometry
Volym: 37
Nummer: 3
Dokumenttyp: Artikel
Förlag: Elsevier B.V.


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.



  • Technology and Engineering


  • VR 2005-4085

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se


Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen