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 polylog 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(log n) query time. In addition to improving the query time, our oracle is much simpler than the previous approach.
No takes yet. Share an insight, caveat, or question.
Dey et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: