| dc.contributor.author |
Dey, Dipan |
|
| dc.contributor.author |
Gupta, Manoj |
|
| dc.contributor.other |
arXiv |
|
| dc.coverage.spatial |
United States of America |
|
| dc.date.accessioned |
2024-02-28T10:27:37Z |
|
| dc.date.available |
2024-02-28T10:27:37Z |
|
| dc.date.issued |
2024-02 |
|
| dc.identifier.citation |
Dey, Dipan and Gupta, Manoj, "Nearly optimal fault tolerant distance oracle", arXiv, Cornell University Library, DOI: arXiv:2402.12832, Feb. 2024. |
|
| dc.identifier.issn |
2331-8422 |
|
| dc.identifier.uri |
https://doi.org/10.48550/arXiv.2402.12832 |
|
| dc.identifier.uri |
https://repository.iitgn.ac.in/handle/123456789/9813 |
|
| dc.description.abstract |
We present an f-fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from [1…W]. Given a set F of f edges, as well as a source node s and a destination node t, our oracle returns the \emph{shortest path} from s to t avoiding F in O((cflog(nW))O(f2)) time, where c>1 is a constant. The space complexity of our oracle is O(f4n2log2(nW)). For a constant f, our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor). |
|
| dc.description.statementofresponsibility |
by Dipan Dey and Manoj Gupta |
|
| dc.language.iso |
en_US |
|
| dc.publisher |
Cornell University Library |
|
| dc.title |
Nearly optimal fault tolerant distance oracle |
|
| dc.type |
Article |
|