In this paper, we consider an evacuation problem in dynamic networks as one of the basic studies on crisis management systems for evacuation guidance of residents against large-scale disasters. We restrict our attention to tree networks and flows such that all the supplies going through a common vertex are sent to a single sink, since everyone has to evacuate fairly and without confusion. We show that the evacuation problem can be solved in polynomial time if the number of sinks is bounded by some constant.
展开▼
