Dey, DipanDipanDeyGupta, ManojManojGupta2025-08-312025-08-312024-09-01[9783959773386]10.4230/LIPIcs.ESA.2024.452-s2.0-85205709660http://repository.iitgn.ac.in/handle/IITG2025/28749We 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 Õ(n²) ¹, 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 Õ(n²) space and O(log n) query time. In addition to improving the query time, our oracle is much simpler than the previous approach.falseDistance Sensitive Oracle | Dual Fault Distance OracleConference PaperSeptember 2024045cpConference Proceeding