Fault-Tolerant Approximate Distance Oracles with a Source Set

Dipan Dey, Telikepalli Kavitha

Our input is an undirected weighted graph $G=(V,E)$ on $n$ vertices along with a source set $S\subseteq V$. The problem is to preprocess $G$ and build a compact data structure su…