An Optimal Algorithm for Weighted Minimax Flow Centers on Trees

Let a tree be given with supplies assigned to its nodes and weights assigned to its edges. The problem considered here is to locate a facility, so that the flow pattern which results from shipping all supplies to the facility, is such that it minimizes the largest weighted flow on any individual edge. First some properties of such facility locations are derived and then a linear time algorithm for their determination along with the associated flow pattern is given.