论文标题
近距离算法，可及性，强烈连接的组件和最短的路径部分动态挖掘图
Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs
论文作者
论文摘要
在本文中，我们提出了新技术来处理基本算法图问题，其中图是指向图形和部分动态的，即进行一系列边缘插入或缺失： - 单源可达性（SSR）， - 强烈连接的组件（SCC）和 - 单源最短路径（SSSP）。 这些问题最近因在各种更复杂和臭名昭著的硬图问题中作为子问题的作用而受到了极大的关注，尤其是计算流量，两部分匹配和切割。 我们的技术导致在各种不同设置中为这些问题的第一个近乎最佳的数据结构。让$ n $表示图表中的顶点数量，用$ m $表示图表中任何版本中的最大边数，我们获得 - 在近距离的总更新时间$ \ tilde {o}（m）$中，将SSR和SCC维护的第一个随机数据结构在删除边缘删除的图中。 - 在总更新时间中，将SSSP保持在总更新时间$ \ tilde {o}（n^2）$中的第一个随机数据结构，该数据结构在密集图中很快。 - SSR和SCC的第一个确定性数据结构，用于进行边缘删除的图形，以及在部分动态图中的SSSP，这些图在$ O（Mn）$总更新时间上改善了1981年的总更新时间，而Shiloach通常被认为是基本障碍。
In this thesis, we present new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edge insertions or deletions: - Single-Source Reachability (SSR), - Strongly-Connected Components (SCCs), and - Single-Source Shortest Paths (SSSP). These problems have recently received an extraordinary amount of attention due to their role as subproblems in various more complex and notoriously hard graph problems, especially to compute flows, bipartite matchings and cuts. Our techniques lead to the first near-optimal data structures for these problems in various different settings. Letting $n$ denote the number of vertices in the graph and by $m$ the maximum number of edges in any version of the graph, we obtain - the first randomized data structure to maintain SSR and SCCs in near-optimal total update time $\tilde{O}(m)$ in a graph undergoing edge deletions. - the first randomized data structure to maintain SSSP in partially dynamic graphs in total update time $\tilde{O}(n^2)$ which is near-optimal in dense graphs. - the first deterministic data structures for SSR and SCC for graphs undergoing edge deletions, and for SSSP in partially dynamic graphs that improve upon the $O(mn)$ total update time by Even and Shiloach from 1981 that is often considered to be a fundamental barrier.
