HIGASHIKAWA Yuya, GOLIN Mordecai. J, KATOH Naoki
IEICE technical report. Theoretical foundations of Computing, 113(371) 93-97, Dec 20, 2013
This paper considers the k-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. Let x denote a k-sink location. Under the optimal evacuation to a given x, any two evacuation paths never cross each other. Additionally, we assume that all evacuees given at the same vertex evacuate to the same sink. Then, there exists a (k-1)-vector d, called (k-1)-divider, such that each component represents the boundary dividing all evacuees between adjacent two sinks into two groups, i.e., one group evacuates to the left sink and the other group evacuates to the right sink. Then, the problem is to find x and d which minimizes the time required for all evacuees on a path divided by d to complete evacuation to x. We present an O(kn log n) time algorithm for the k-sink location problem in a dynamic path network with uniform capacity, where n is the number of vertices in the given network.