TY - GEN

T1 - An efficient algorithm for the evacuation problem in a certain class of a network with uniform path-lengths

AU - Kamiyama, Naoyuki

AU - Katoh, Naoki

AU - Takizawa, Atsushi

PY - 2007

Y1 - 2007

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=38149096205&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38149096205&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-72870-2_17

DO - 10.1007/978-3-540-72870-2_17

M3 - Conference contribution

AN - SCOPUS:38149096205

SN - 9783540728689

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 178

EP - 190

BT - Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings

PB - Springer Verlag

T2 - 3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007

Y2 - 6 June 2007 through 8 June 2007

ER -