Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning
Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning
复制标题
用于应急计划的增量和全动态子图连接
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Neumann
中科院分区：
文献类型：
--
作者：
Monika Henzinger;S. Neumann
在过去的10年中，在紧急计划或敏感性设置中研究动态图问题已经变得流行：而不是考虑一般的完全动态问题，我们只需要处理大小为d的单批更新;更新后，我们必须回答查询。
本文研究了灵敏度为d的动态子图连通性问题：给定一个图，其中一些顶点是激活的，一些顶点是去激活的。之后，我们得到一个更新，其中最多$d$个顶点的状态发生了变化。然后，我们得到一个序列的连通性查询的激活顶点的子图。
我们提出了这个问题的第一个完全动态的算法，它的更新和查询时间只比最好的递减算法略差。此外，我们提出了第一个增量算法，这是紧相对于最好的已知的条件下限，而且，该算法是简单的，我们相信它是可实现的，在实践中是有效的。
During the last 10 years it has become popular to study dynamic graph problems in a emergency planning or sensitivity setting: Instead of considering the general fully dynamic problem, we only have to process a single batch update of size d; after the update we have to answer queries.
In this paper, we consider the dynamic subgraph connectivity problem with sensitivity d: We are given a graph of which some vertices are activated and some are deactivated. After that we get a single update in which the states of up to $d$ vertices are changed. Then we get a sequence of connectivity queries in the subgraph of activated vertices.
We present the first fully dynamic algorithm for this problem which has an update and query time only slightly worse than the best decremental algorithm. In addition, we present the first incremental algorithm which is tight with respect to the best known conditional lower bound; moreover, the algorithm is simple and we believe it is implementable and efficient in practice.