Approximate distance oracles for graphs with dense clusters

Summary, in English

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: Mattias Andersson; J Gudmundsson; Christos Levcopoulos
• Department/s: Computer Science
• Publishing year: 2004
• Language: English
• Pages: 53-64
• Publication/Series: Algorithms and Computation / Lecture notes in computer science
• Volume: 3341
• Links: http://dx.doi.org/10.1007/978-3-540-30551-4_7
• Document type: Conference paper
• Publisher: Springer
• Topic: Computer Science
• Conference name: 15th International Symposium, ISAAC 2004
• Conference date: 2004-12-20 - 2004-12-22
• Conference place: Hong Kong, China
• Status: Published
• Project: VR 2002-4049
• ISBN/ISSN/Other: ISSN: 0302-9743; ISSN: 1611-3349