Nearly Optimal Fault Tolerant Distance Oracle

We present an f -fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from [1 . . . W ]. Given a set F of f edges, as well as a source node s and a destination node t, our oracle returns the shortest path from s to t avoiding F in O((c f log(nW )) O( f 2 ) ) time, where c > 1 is a constant. The space complexity of our oracle is O( f 4 n 2 log 2 (nW )). For a constant f , our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor).