Key points are not available for this paper at this time.
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 ( (cf (nW) ) ^O (f²) ) time, where c > 1 is a constant. The space complexity of our oracle is O (f⁴n²² (nW) ). For a constant f, our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor).
Dey et al. (Tue,) studied this question.