TY - JOUR

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

AU - Kamiyama, Naoyuki

AU - Katoh, Naoki

AU - Takizawa, Atsushi

N1 - Funding Information:
We appreciate the comments of anonymous reviewers who helped in improving the presentation of this paper. The first author is supported by JSPS Research Fellowships for Young Scientists. The second and third authors are supported by the project New Horizons in Computing, Grant-in-Aid for Scientific Research on Priority Areas, MEXT Japan, and by Grant-in-Aid for Scientific Research (C), JSPS.

PY - 2009/10/28

Y1 - 2009/10/28

N2 - In this paper, we consider the evacuation problem in 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 [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36-62] 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 network with a sink s such that (i) for each vertex v ≠ s the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v ≠ s the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372-2379]. We propose an efficient algorithm for this network problem.

AB - In this paper, we consider the evacuation problem in 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 [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36-62] 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 network with a sink s such that (i) for each vertex v ≠ s the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v ≠ s the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372-2379]. We propose an efficient algorithm for this network problem.

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

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

U2 - 10.1016/j.dam.2009.04.007

DO - 10.1016/j.dam.2009.04.007

M3 - Article

AN - SCOPUS:70350060332

SN - 0166-218X

VL - 157

SP - 3665

EP - 3677

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 17

ER -