Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks
Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks
复制标题
DOI：
10.1007/978-3-319-62127-2_12
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
B. Bhattacharya;M. Golin;Yuya Higashikawa;T. Kameda;N. Katoh
中科院分区：
文献类型：
--
作者：
B. Bhattacharya;M. Golin;Yuya Higashikawa;T. Kameda;N. Katoh
本文研究了在具有n个顶点的动态流路网络上定位ksins的问题，使得疏散完成时间最小化。我们的两个算法分别在和时间上运行。当所有边的容量相同时，我们还提出了两个分别在时间和时间上运行的算法。这些算法一起改进了以前最有效的算法，它们分别在一般和均匀边容量的情况下具有时间复杂度[1]和O（kn）[11]。上述结果是通过在预处理过程中以策略性的方式组织子路径的相关数据来实现的，并且通过以有效的方式提取/合并它们来获得最终结果。
We address the problem of locatingksinks on dynamic flow path networks withnvertices in such a way that the evacuation completion time to them is minimized. Our two algorithms run inandtime, respectively. When all edges have the same capacity, we also present two algorithms which run intime andtime, respectively. These algorithms together improve upon the previously most efficient algorithms, which have time complexities[1] andO(kn) [11], in the general and uniform edge capacity cases, respectively. The above results are achieved by organizing relevant data for subpaths in a strategic way during preprocessing, and the final results are obtained by extracting/merging them in an efficient manner.