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 log(nW))O(f2)) time, where c > 1 is a constant. The space complexity of our oracle is O(f4n2log2 (nW)). For a constant f, our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor).
Dey et al. (Mon,) studied this question.