An O(nlog2n) algorithm for the optimal sink location problem in dynamic tree networks

In this paper, we consider a sink location in a dynamic network which consists of a graph with capacities and transit times on its arcs. Given a dynamic network with initial supplies at vertices, the problem is to find a vertex vv as a sink in the network such that we can send all the initial supplies to vv as quickly as possible. We present an O(nlog2n) time algorithm for the sink location problem, in a dynamic network of tree structure where n   is the number of vertices in the network. This improves upon the existing O(n2)O(n2)-time bound [S. Mamada, K. Makino, S. Fujishige, Optimal sink location problem for dynamic flows in a tree network, IEICE Trans. Fundamentals E85-A (2002) 1020–1025]. As a corollary, we also show that the quickest transshipment problem can be solved in O(nlog2n) time if a given network is a tree and has a single sink. Our results are based on data structures for representing tables (i.e., sets of intervals with their height), which may be of independent interest.