| dc.contributor.author |
Dey, Dipan |
|
| dc.contributor.author |
Gupta, Manoj |
|
| dc.contributor.other |
32nd Annual European Symposium on Algorithms (ESA 2024) |
|
| dc.coverage.spatial |
United Kingdom |
|
| dc.date.accessioned |
2024-10-30T10:20:32Z |
|
| dc.date.available |
2024-10-30T10:20:32Z |
|
| dc.date.issued |
2024-09-02 |
|
| dc.identifier.citation |
Dey, Dipan and Gupta, Manoj, "Near optimal dual fault tolerant distance oracle", in the 32nd Annual European Symposium on Algorithms (ESA 2024), London, GB, Sep. 02-04, 2024. |
|
| dc.identifier.uri |
https://drops.dagstuhl.de/storage/00lipics/lipics-vol308-esa2024/LIPIcs.ESA.2024.45/LIPIcs.ESA.2024.45.pdf |
|
| dc.identifier.uri |
https://repository.iitgn.ac.in/handle/123456789/10679 |
|
| dc.description.abstract |
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(n2) 1, 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(n2) space and O(logn) query time. In addition to improving the query time, our oracle is much simpler than the previous approach. |
|
| dc.description.statementofresponsibility |
by Dipan Dey and Manoj Gupta |
|
| dc.language.iso |
en_US |
|
| dc.subject |
Distance sensitive oracle |
|
| dc.subject |
Dual fault distance oracle |
|
| dc.title |
Near optimal dual fault tolerant distance oracle |
|
| dc.type |
Conference Paper |
|