Approximate Distance Oracles for Graphs with Dense Clusters

摘要

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 ∪ F_2). We present a data structure of size O(M~2 + |V| log |V|) that answers (1 + ε)-approximate shortest path queries in G in constant time, where ε > 0 is constant.