Maintaining exact distances under multiple edge failures

DOI10.1145/3519935.3520002arXiv2111.03360OpenAlexW3211891880MaRDI QIDQ6083561FDOQ6083561

Ran Duan, Hanlin Ren

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We present the first compact distance oracle that tolerates multiple failures and maintains exact distances. Given an undirected weighted graph $G=(V,E)$ and an arbitrarily large constant $d$, we construct an oracle that given vertices $u,vinV$ and a set of $d$ edge failures $D$, outputs the exact distance between $u$ and $v$ in $G-D$ (that is, $G$ with edges in $D$ removed). Our oracle has space complexity $O(d{n}^4)$ and query time $d^{O(d)}$. Previously, there were compact approximate distance oracles under multiple failures [Chechik, Cohen, Fiat, and Kaplan, SODA'17; Duan, Gu, and Ren, SODA'21], but the best exact distance oracles under $d$ failures require essentially $Omega(n^d)$ space [Duan and Pettie, SODA'09]. Our distance oracle seems to require $n^{Omega(d)}$ time to preprocess; we leave it as an open question to improve this preprocessing time.

Full work available at URL: https://arxiv.org/abs/2111.03360

zbMATH Keywords

shortest pathsdynamic data structuresdistance sensitivity oracles

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (3)

• Approximate distance sensitivity oracles in subquadratic space
• Compact distance oracles with large sensitivity and low stretch
• Maintaining approximate extent measures of moving points

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Edge fault tolerance in graphs 👍 👎
• Maintaining approximate extent measures of moving points 👍 👎
• Tolerating faulty edges in a multi-dimensional mesh 👍 👎
• Numerical Software with Result Verification 👍 👎
• Fault-tolerant edge metric dimension of certain families of graphs 👍 👎
• Random distances and edge correction 👍 👎

This page was built for publication: Maintaining exact distances under multiple edge failures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083561)