AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

Given a graph G with non-negative edge lengths whose vertices are assigned a label from a set of labels L, we show how to construct a compact distance oracle that answers queries of the form: "What is d(v,l)?", where v is a vertex in the graph, l is a vertex label, and d(v,l) is the distance (length of a shortest path) between v and the closest vertex labeled l 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 show how to extend our solution to dynamic oracles that support label updates in sublinear time.

Danny Hermelin

--email hidden

passcode not visible

logged in users only

Compact data structures, all-pairs shortest paths