| An Efficient Algorithm for the Evacuation Problem in a Certain Class of a Network with Uniform Path-Lengths (Algorithmic Aspects in Information and Management) (2008) | |||||||||||||
Abstract | |||||||||||||
| Algorithmic aspects in information and management : Third International Conference, AAIM 2007, Portland, OR, USA, June 6-8, 2007 : proceedings : (Lecture notes in computer science ; 4508). Proc. of 3rd Int. Conf. on Algorithmic Aspect in Information and Management. (AAIM 2007). In this paper, we consider the evacuation problem for a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [1] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a dynamic network with a single sink s such that (i) for each vertex v the sum of transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. We propose an efficient algorithm for this network problem. This class of networks is a generalization of the grid network studied in the paper [2]. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||