Approximate distance oracles for graphs with dense clusters

Summary, in English

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.

• Författare: Mattias Andersson; Joachim Gudmundsson; Christos Levcopoulos
• Avdelning/ar: Computer Science
• Publiceringsår: 2007
• Språk: Engelska
• Sidor: 142-154
• Publikation/Tidskrift/Serie: Computational Geometry
• Volym: 37
• Issue: 3
• Länkar: http://dx.doi.org/10.1016/j.comgeo.2004.12.011
• Dokumenttyp: Artikel i tidskrift
• Förlag: Elsevier
• Ämne: Computer Science
• Status: Published
• Projekt: VR 2005-4085
• ISBN/ISSN/Övrigt: ISSN: 0925-7721