TY - GEN
T1 - A polynomial-time algorithm for the universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths
AU - Kamiyama, Naoyuki
AU - Katoh, Naoki
PY - 2009
Y1 - 2009
N2 - In this paper, we consider the universally quickest transshipment problem in a dynamic network where each arc has not only a capacity but also a transit time. The problem asks for minimizing the time when the last supply reaches the sink as well as simultaneously maximizing the amount of supply which has reached the sink at every time step. In this paper, we propose a polynomial-time algorithm for the problem in the class of dynamic networks which is a generalization of grid networks with uniform capacity and uniform transit time.
AB - In this paper, we consider the universally quickest transshipment problem in a dynamic network where each arc has not only a capacity but also a transit time. The problem asks for minimizing the time when the last supply reaches the sink as well as simultaneously maximizing the amount of supply which has reached the sink at every time step. In this paper, we propose a polynomial-time algorithm for the problem in the class of dynamic networks which is a generalization of grid networks with uniform capacity and uniform transit time.
UR - http://www.scopus.com/inward/record.url?scp=75649128725&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=75649128725&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-10631-6_81
DO - 10.1007/978-3-642-10631-6_81
M3 - Conference contribution
AN - SCOPUS:75649128725
SN - 3642106307
SN - 9783642106309
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 802
EP - 811
BT - Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
T2 - 20th International Symposium on Algorithms and Computation, ISAAC 2009
Y2 - 16 December 2009 through 18 December 2009
ER -