| dc.contributor.author |
Dey, Dipan |
|
| dc.contributor.author |
Gupta, Manoj |
|
| dc.coverage.spatial |
United States of America |
|
| dc.date.accessioned |
2024-07-11T15:27:49Z |
|
| dc.date.available |
2024-07-11T15:27:49Z |
|
| dc.date.issued |
2024-07 |
|
| dc.identifier.citation |
Dey, Dipan and Gupta, Manoj, "Near optimal dual fault tolerant distance oracle", arXiv, Cornell University Library, DOI: arXiv:2406.19709, Jul. 2024. |
|
| dc.identifier.uri |
https://arxiv.org/abs/2406.19709 |
|
| dc.identifier.uri |
https://repository.iitgn.ac.in/handle/123456789/10227 |
|
| 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 $\Tilde{O}(n^2)$ \footnote{$\Tilde{O}$ hides polylogn 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 $\Tilde{O}(n^2)$ 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.publisher |
Cornell University Library |
|
| dc.title |
Near optimal dual fault tolerant distance oracle |
|
| dc.type |
Article |
|
| dc.relation.journal |
arXiv |
|