0
[2402.12832] Nearly Optimal Fault Tolerant Distance Oracle
source link: https://arxiv.org/abs/2402.12832
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 20 Feb 2024 (v1), last revised 26 Mar 2024 (this version, v4)]
Nearly Optimal Fault Tolerant Distance Oracle
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).
| Comments: | accepted in STOC, 2024 |
| Subjects: | Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2402.12832 [cs.DS] |
| (or arXiv:2402.12832v4 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2402.12832 |
Submission history
From: Dipan Dey [view email][v1] Tue, 20 Feb 2024 08:58:37 UTC (85 KB)
[v2] Wed, 21 Feb 2024 10:24:10 UTC (96 KB)
[v3] Mon, 26 Feb 2024 15:59:24 UTC (97 KB)
[v4] Tue, 26 Mar 2024 09:08:06 UTC (97 KB)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK