| dc.contributor.author |
Dey, Dipan |
|
| dc.contributor.author |
Gupta, Manoj |
|
| dc.contributor.other |
56th Annual ACM Symposium on Theory of Computing (STOC 2024) |
|
| dc.coverage.spatial |
Canada |
|
| dc.date.accessioned |
2024-06-21T06:42:15Z |
|
| dc.date.available |
2024-06-21T06:42:15Z |
|
| dc.date.issued |
2024-06-24 |
|
| dc.identifier.citation |
Dey, Dipan and Gupta, Manoj, "Nearly optimal fault tolerant distance Oracle", in the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), Vancouver, CA, Jun. 24-28, 2024. |
|
| dc.identifier.uri |
https://doi.org/10.1145/3618260.3649697 |
|
| dc.identifier.uri |
https://repository.iitgn.ac.in/handle/123456789/10158 |
|
| 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 shortest path from s to t avoiding F in O((cf log(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 |
Association for Computing Machinery (ACM) |
|
| dc.subject |
Replacement paths |
|
| dc.subject |
Fault-tolerant |
|
| dc.subject |
Distance Oracle |
|
| dc.title |
Nearly optimal fault tolerant distance Oracle |
|
| dc.type |
Conference Paper |
|