Constrained pairwise and center-star sequences alignment problems

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(n^3\log n)\) time algorithm.