论文标题
确定性的灵敏度甲环直径，偏心率和所有对距离
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
论文作者
论文摘要
在存在瞬态边缘故障的情况下，我们在有向图中的极端和成对距离构建数据结构。 Henzinger等。 [ITCS 2017]启动了直径和顶点偏心率的耐断层（敏感性）甲虫的研究。我们将其特别关注太空效率扩展。我们介绍了几种新的数据结构，其中包括第一个容忍偏心的偏心度甲骨文，用于亚皮ubi骨空间中的双重故障。我们进一步证明了近似值与空间与直径与容忍矫正器的空间权衡的限制。它们突出显示了无向图和有向图的数据结构之间的关键差异。 最初，我们的口腔是随机依靠用于敏感性分析的采样技术。在Alon，Chechik和Cohen [ICALP 2019]以及Karthik和Parter [Soda 2021]的工作基础上，我们开发了一个分层框架，以衍生易于故障数据结构。我们首先将其应用于我们自己的直径和偏心度牙齿上，然后通过从文献中脱离算法来显示其多功能性：Ren [JCSS 2022]的距离灵敏度Oracle和Chechik和Magen的单源替换路径算法[ICALP 2020]。这样，我们获得了第一个确定性的距离灵敏度甲骨文，并使用亚立方体预处理时间。
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen [ICALP 2019] as well as Karthik and Parter [SODA 2021], we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter and eccentricity oracles and then show its versatility by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren [JCSS 2022] and the Single-Source Replacement Path algorithm of Chechik and Magen [ICALP 2020]. This way, we obtain the first deterministic distance sensitivity oracle with subcubic preprocessing time.
