An Efficient Algorithm for Evacuation Problem in Dynamic Network Flows with Uniform Arc Capacity
Noriaki Kamiyama · IEICE Transactions on Information and Systems · 2006
In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs.We present an O(n log n) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network.