Minimax regret vertex 2-sink location problem in dynamic path networks

This paper considers the minimax regret vertex 2-sink location problem in a dynamic path network with positive edge lengths and uniform edge capacity. Let P be an undirected path graph of n vertices, and the weight (initial supply) of every vertex is known as an interval. The problem is to find two vertices x and y as two sinks on the path such that all the weights can evacuate to x and y with minimum regret of evacuation time in case of an emergency for any possible weight distribution. We present an O(n3logn) time algorithm.