Minsum k-Sink Problem on Path Networks
Minsum k-Sink Problem on Path Networks
复制标题
DOI：
10.1016/j.tcs.2019.05.047
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
R. Benkoczi;B. Bhattacharya;Yuya Higashikawa;T. Kameda;N. Katoh
中科院分区：
文献类型：
--
作者：
R. Benkoczi;B. Bhattacharya;Yuya Higashikawa;T. Kameda;N. Katoh
我们考虑在具有一般边容量且最小化所有疏散人员的疏散时间总和的路径网络上寻找一组k个汇点的问题。首先给出了边容量不均匀时的O(k nlog4n)时间算法，其中n为顶点数.然后给出了边容量相等时的O(k n log3n)时间算法。对于k=1且边容量不均匀的特殊情况，我们还给出了一个O(nlogn)时间算法。
We consider the problem of locating a set of k sinks on a path network with general edge capacities that minimizes the sum of the evacuation times of all evacuees. We first present an O (k n log 4 n) time algorithm when the edge capacities are non-uniform, where n is the number of vertices. We then present an O (k n log 3 n) time algorithm when the edge capacities are uniform. We also present an O (n log n) time algorithm for the special case where k= 1 and the edge capacities are non-uniform.