Nearly Optimal Fault Tolerant Distance Oracle
This provides a theoretical solution for robust shortest path queries in networks with edge failures, though it is incremental as it builds on existing fault-tolerant distance oracle research.
The paper tackles the problem of computing shortest paths in undirected weighted graphs while avoiding up to f edge failures, presenting an f-fault tolerant distance oracle with query time O((cf log(nW))^{O(f^2)}) and space O(f^4n^2 log^2(nW)). For constant f, the oracle is nearly optimal in space and time up to logarithmic factors.
We present an $f$-fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from $[1 \dots W]$. Given a set $F$ of $f$ edges, as well as a source node $s$ and a destination node $t$, our oracle returns the \emph{shortest path} from $s$ to $t$ avoiding $F$ in $O((cf \log (nW))^{O(f^2)})$ time, where $c > 1$ is a constant. The space complexity of our oracle is $O(f^4n^2\log^2 (nW))$. For a constant $f$, our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor).