Maintaining exact distances under multiple edge failures

DOI10.1145/3519935.3520002MaRDI QIDQ6083561zbMATH OpenOpenAlexFDO

Authors 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)

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)

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.

Recommendations

• Preserving distances in very faulty graphs
• Random distances and edge correction
• Generic single edge fault tolerant exact distance oracle
• Edge fault tolerance in graphs
• Tolerating faulty edges in a multi-dimensional mesh
• Numerical Software with Result Verification
• Maintaining approximate extent measures of moving points
• Fault-tolerant edge metric dimension of certain families of graphs

Cited in

(5)

• Approximate distance sensitivity oracles in subquadratic space
• Compact distance oracles with large sensitivity and low stretch
• Maintaining approximate extent measures of moving points
• Near optimal dual fault tolerant distance oracle
• A nearly linear time construction of approximate single-source distance sensitivity oracles

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)