  Let $G=(V,E)$ be a graph modelling a building or road network in which edges
have-both travel times (lengths) and capacities associated with them. An edge's
capacity is the number of people that can enter that edge in a unit of time.
  In emergencies, people evacuate towards the exits. If too many people try to
evacuate through the same edge, congestion builds up and slows down the
evacuation.
  Graphs with both lengths and capacities are known as Dynamic Flow networks.
An evacuation plan for $G$ consists of a choice of exit locations and a
partition of the people at the vertices into groups, with each group evacuating
to the same exit. The evacuation time of a plan is the time it takes until the
last person evacuates. The $k$-sink evacuation problem is to provide an
evacuation plan with $k$ exit locations that minimizes the evacuation time. It
is known that this problem is NP-Hard for general graphs but no polynomial time
algorithm was previously known even for the case of $G$ a tree. This paper
presents an $O(n k^2 \log^5 n)$ algorithm for the $k$-sink evacuation problem
on trees. Our algorithms also apply to a more general class of problems, which
we call minmax tree facility location.
