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 -