Given a graph G = (V,E) with non-negative edge lengths whose vertices are assigned a label from L = {λ1, . . ., λl}, we construct a compact distance oracle that answers queries of the form: "What is δ(v, λ)?", where v ∈ V is a vertex in the graph, λ ∈ L a vertex label, and δ(v, λ) is the distance (length of a shortest path) between v and the closest vertex labeled λ in G. We formalize this natural problem and provide a hierarchy of approximate distance oracles that require subquadratic space and return a distance of constant stretch. We also extend our solution to dynamic oracles that handle label changes in sublinear time.
['Danny Hermelin', 'Avivit Levy', 'Oren Weimann', 'Raphael Yuster']
Distance oracles for vertex-labeled graphs