Faster Algorithms for Evacuation Problems in Networks with the Small Degree Sink and Uniformly Capacitated Edges

In this paper, we propose new algorithms for the evacuation problems defined on dynamic flow networks. A dynamic flow network consists of a directed graph where source nodes are given supplies (i.e., the number of evacuees) and a single sink node is given a demand (i.e., the maximum number of acceptable evacuees). The evacuation problem asks for a dynamic flow that sends all supplies from sources to the sink so as to satisfy its demand in the minimum feasible time horizon. For this problem, the current best algorithms are developed by Schl\"oter (2018) and Kamiyama (2019). Their algorithms run in strongly polynomial time, but is high-order polynomial. This is because their algorithms use the submodular function minimization as a subroutine. In this paper, we propose new algorithms which do not explicitly execute the submodular function minimization, and prove our algorithms run faster than the ones by Schl\"oter (2018) and Kamiyama (2019) when an input network is restricted so that the sink has a small in-degree and every edge has the same capacity.