The quickest flow problem

Consider a network=(G, c, ) whereG=(N, A) is a directed graph andc_ij and_ij, respectively, denote the capacity and the transmission time of arc (i, j) A. The quickest flow problem is then to determine for a given value the minimum numberT() of time units that are necessary to transmit (send) units of flow in from a given sources to a given sinks.In this paper we show that the quickest flow problem is closely related to the maximum dynamic flow problem and to linear fractional programming problems. Based on these relationships we develop several polynomial algorithms and a strongly polynomial algorithm for the quickest flow problem.Finally we report computational results on the practical behaviour of our metholds. It turns out that some of them are practically very efficient and well-suited for solving large problem instances.Partial financial support by the Air Force Office of Scientific Research under grants AFOSR-89-0512 and AFOSR-90-0008 is gratefully acknowledged by the first author.