标题： 具有源集的容错近似距离预言器 显示英文标题

标题： Fault-Tolerant Approximate Distance Oracles with a Source Set

摘要： 我们的输入是一个无向加权图$G = (V,E)$在$n$个顶点上，以及一个源集$S\subseteq V$。 问题是在预处理$G$的基础上构建一个紧凑的数据结构，使得在查询$Qu(s,v,f)$时，其中$(s,v) \in S\times V$和$f$是任何故障边，我们可以快速找到$s$-$v$距离的一个良好估计（即在较小的乘法拉伸范围内）在$G-f$中。 我们使用Bil{ò}等人( STACS 2018 )的工作中的容错$ST$-距离Oracle，来构建一个大小为$\widetilde{O}(|S|n + n^{3/2})$的$S\times V$近似距离Oracle或{\em 按源}近似距离Oracle，其乘法拉伸不超过5。 我们构建了另一个大小为$\widetilde{O}(|S|n + n^{4/3})$的容错源wise近似距离Oracle，其乘法拉伸不超过13。 这两个Oracle的查询回答时间为$O(1)$。 显示英文摘要

摘要： Our input is an undirected weighted graph $G = (V,E)$ on $n$ vertices along with a source set $S\subseteq V$. The problem is to preprocess $G$ and build a compact data structure such that upon query $Qu(s,v,f)$ where $(s,v) \in S\times V$ and $f$ is any faulty edge, we can quickly find a good estimate (i.e., within a small multiplicative stretch) of the $s$-$v$ distance in $G-f$. We use a fault-tolerant $ST$-distance oracle from the work of Bil{\`{o}} et al. (STACS 2018) to construct an $S\times V$ approximate distance oracle or {\em sourcewise} approximate distance oracle of size $\widetilde{O}(|S|n + n^{3/2})$ with multiplicative stretch at most 5. We construct another fault-tolerant sourcewise approximate distance oracle of size $\widetilde{O}(|S|n + n^{4/3})$ with multiplicative stretch at most 13. Both the oracles have $O(1)$ query answering time.