Improved Distance Oracles and Spanners for Vertex-Labeled Graphs

Shiri Chechik

Consider an undirected weighted graph G=(V,E) with |V|=n and |E|=m, where each vertex v is assigned a label from a set L of \ell labels. We show how to construct a compact distance…