Paper Info
Title
Almost Linear Time Algorithms For Minsum K-Sink Problems On Dynamic Flow Path Networks
Abstract
We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and positive vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. In the dynamic flow network, given particular points on edges or vertices, called sinks, all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i.e., the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: the confluent flow model and the non-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm. (C)) 2021 The Author(s). Published by Elsevier B.V.
Year
DOI
Venue
2021
10.1016/j.tcs.2021.05.003
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Dynamic flow networks, Facility location problems, Minimum k-link path problem, Persistent data structures
Journal
873
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Yuya Higashikawa16412.71
naoki katoh21101187.43
Junichi Teruyama3135.67
Koji Watase400.34