Minimax regret 1-sink location problem with accessibility in dynamic general networks

In this study, we consider the minimax regret 1-sink location problem with accessibility, where all of the weights should always evacuate to the nearest sink point along the shortest path in a dynamic general network with positive edge lengths and uniform edge capacity. Let G=(V,E) be an undirected connected simple graph with n vertices and m edges. Each vertex has a weight that is not known exactly but the interval to which it belongs is given. A particular assignment of a weight to each vertex is called a scenario. The problem requires that a point x should be found as the sink on the graph and all the weights evacuate to x such that the maximum regret for all possible scenarios is minimized. We present an O(m²n³) time algorithm to solve this problem.