Compact Distance Oracles with Large Sensitivity and Low Stretch

Davide Bilò, Keerti Choudhary, Sarel Cohen +3

An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $\sigma \ge 1$ is a data structure that preprocesses an input graph $G$. When queried with the triple $(s,t,F…