Key points are not available for this paper at this time.
We present a dual fault-tolerant distance oracle for undirected and unweighted graphs. Given a set F of two edges, as well as a source node s and a destination node t, our oracle returns the length of the shortest path from s to t that avoids F in O (1) time with a high probability. The space complexity of our oracle is O (n²) O hides poly n factor, making it nearly optimal in terms of both space and query time. Prior to our work, Pettie and Duan SODA 2009 designed a dual fault-tolerant distance oracle that required O (n²) space and O (n) query time. In addition to improving the query time, our oracle is much simpler than the previous approach.
Dey et al. (Fri,) studied this question.