Mathematics of Operations Research · 2000 · 306 citations · 25 references
Natural SciencesComputer ScienceAlgorithmsOptimizationTransportationCombinatorial OptimizationGraph AlgorithmsNetwork Flow AlgorithmsNetwork FlowsNetwork OptimizationTransportation ProblemsDynamic Network FlowsEvacuationIntegral FlowNetwork Flow ProblemsPolynomial Time ComplexityPolynomial-time AlgorithmsTransshipment Problem
A dynamic network consists of a graph with capacities and transit times on its edges. The quickest transshipment problem is defined by a dynamic network with several sources and sinks; each source has a specified supply and each sink has a specified demand. The problem is to send exactly the right amount of flow out of each source and into each sink in the minimum overall time. Variations of the quickest transshipment problem have been studied extensively; the special case of the problem with a single sink is commonly used to model building evacuation. Similar dynamic network flow problems have numerous other applications; in some of these, the capacities are small integers and it is important to find integral flows. There are no polynomial-time algorithms known for most of these problems. In this paper we give the first polynomial-time algorithm for the quickest transshipment problem. Our algorithm provides an integral optimum flow. Previously, the quickest transshipment problem could only be solved efficiently in the special case of a single source and single sink.
25
A new approach to the maximum-flow problem
Andrew V. Goldberg, Robert E. Tarjan · Journal of the ACM · 1988 · 1.9K citations · Full text
A survey of dynamic network flows
Jay E. Aronson · Annals of Operations Research · 1989 · 293 citations