1-2hit |
Satoko MAMADA Kazuhisa MAKINO Satoru FUJISHIGE
In this paper we consider a compound problem of dynamic flows and sink location in a tree network. Given a dynamic flow network of tree structure with initial supplies at vertices, the problem is to find a vertex v as a sink in the network such that we can send all the initial suplies to v as quick as possible. This problem can be regarded as a dynamic flow version of the 1-center problem in a tree network. We present an O(n2) time algorithm for the sink location problem, where n is the number of vertices in the network.
We first describe fundamental results about submodular functions and submodular flows, which lay a basis for devising efficient algorithms for submodular flows. We then give a comprehensive survey on algorithms for submodular flows and show some possible future research directions.