Du är här

Approximate distance oracles for graphs with dense clusters

Publiceringsår: 2004
Språk: Engelska
Sidor: 53-64
Publikation/Tidskrift/Serie: Algorithms and Computation / Lecture notes in computer science
Volym: 3341
Dokumenttyp: Konferensbidrag
Förlag: Springer


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.



  • Technology and Engineering


15th International Symposium, ISAAC 2004
Hong Kong, China
  • VR 2002-4049
  • ISSN: 0302-9743

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

LERU logotype U21 logotype

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