Name
Title | ||
|---|---|---|
An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths |
Abstract | ||
|---|---|---|
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, E. 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 vs the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex vs 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.dam.2009.04.007 | Discrete Applied Mathematics |
Keywords | Field | DocType |
network problem,evacuation problem,transit time,uniform path-length,quickest transshipment problem,arcs incident,certain class,efficient algorithm,grid network,uniform path-lengths,dynamic network,b. hoppe,dynamic network flow,faster algorithm,polynomial time,directed graph | Dynamic network analysis,Discrete mathematics,Combinatorics,Polynomial,Vertex (geometry),Queue,Directed graph,Algorithm,Time complexity,Transshipment problem,Digraph,Mathematics | Journal |
Volume | Issue | ISSN |
157 | 17 | Discrete Applied Mathematics |
Citations | PageRank | References |
12 | 0.89 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Naoyuki Kamiyama | 1 | 80 | 23.40 |
| naoki katoh | 2 | 1101 | 187.43 |
| Atsushi Takizawa | 3 | 50 | 5.45 |