A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles

Kaito Harada, Naoki Kitamura, Taisuke Izumi +1

An \emph{$\hat{I}\pm$-approximate vertex fault-tolerant distance sensitivity oracle} (\emph{$\hat{I}\pm$-VSDO}) for a weighted input graph $G=(V,E,w)$ and a source vertex $s\in V$ is the data s…