Minsum k-Sink Problem on Path Networks
share
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(kn^4n) time algorithm when the edge capacities are non-uniform, where n is the number of vertices. We then present an O(kn^3 n) time algorithm when the edge capacities are uniform. We also present an O(n n) time algorithm for the special case where k=1 and the edge capacities are non-uniform.
READ FULL TEXT