Deterministic Fully Dynamic SSSP and More
Deterministic Fully Dynamic SSSP and More
复制标题
确定性全动态 SSSP 等
DOI：
10.1109/focs57990.2023.00142
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Adam Karczmarz
中科院分区：
文献类型：
--
作者：
Jan van den Brand;Adam Karczmarz
我们提出了第一个非平凡的完全动态算法保持精确的单源距离在未加权图。这解决了Sankowski [COCOON 2005]和货车den Brand和Nanongkai [FOCS 2019]提出的一个未决问题。以前的全动态单源距离数据结构都是近似的，但到目前为止，只能排除多项式加权图的精确设置的非平凡动态算法（Abboud和Vassilevska威廉姆斯，[FOCS 2014]）。精确的未加权的情况下仍然是主要的情况下，既不是一个次二次动态算法，也不是一个二次的下限是know. We的动态算法工作在有向图，是确定性的，并可以报告一个单源最短路径树在次二次时间以及。因此，我们还获得了第一个具有次二次更新和查询时间的可达性（传递闭包）的确定性完全动态数据结构。这回答了货车登布兰德、Nanongkai和Saranurak [FOCS 2019]的一个开放问题。最后，使用相同的框架，我们得到了第一个完全动态的数据结构，保持所有对$（1+\omega）$-近似距离内非平凡的子$n^{\omega}$最坏情况下的更新时间，同时支持最佳时间近似最短路径报告。这种数据结构也是确定性的，因此意味着第一个已知的非平凡的确定性最坏情况下的边界重新计算的传递闭包的有向图。
We present the first non-trivial fully dynamic algorithm maintaining exact single-source distances in unweighted graphs. This resolves an open problem stated by Sankowski [COCOON 2005] and van den Brand and Nanongkai [FOCS 2019]. Previous fully dynamic single-source distances data structures were all approximate, but so far, non-trivial dynamic algorithms for the exact setting could only be ruled out for polynomially weighted graphs (Abboud and Vassilevska Williams, [FOCS 2014]). The exact unweighted case remained the main case for which neither a subquadratic dynamic algorithm nor a quadratic lower bound was known.Our dynamic algorithm works on directed graphs and is deterministic, and can report a single-source shortest paths tree in subquadratic time as well. Thus we also obtain the first deterministic fully dynamic data structure for reachability (transitive closure) with subquadratic update and query time. This answers an open problem of van den Brand, Nanongkai, and Saranurak [FOCS 2019]. Finally, using the same framework we obtain the first fully dynamic data structure maintaining all-pairs $(1+\epsilon)$-approximate distances within non-trivial sub-$n^{\omega}$ worst-case update time while supporting optimal-time approximate shortest path reporting at the same time. This data structure is also deterministic and therefore implies the first known non-trivial deterministic worst-case bound for recomputing the transitive closure of a digraph.
确定性近线性时间内的递减全对最短路径
DOI：
10.1145/3406325.3451025
发表时间：
2021
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Chuzhoy, Julia
通讯作者：
Chuzhoy, Julia
DOI：
10.1137/1.9781611976465.110
发表时间：
2021
期刊：
2021
影响因子：
--
作者：
Bergamaschi, Thiago;Henzinger, Monika;Probst Gutenberg, Maximilian;Williams, Virginia Vassilevska;Wein, Nicole
通讯作者：
Wein, Nicole
通过短周期去除来近似 p 的硬度：周期检测、距离预言等等
DOI：
10.1145/3519935.3520066
发表时间：
2022
期刊：
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Abboud, Amir;Bringmann, Karl;Khoury, Seri;Zamir, Or
通讯作者：
Zamir, Or