About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Discrete Applied Mathematics
Paper
Monge and feasibility sequences in general flow problems
Abstract
In a feasible transportation problem, there is always an ordering of the arcs such that greedily sending maximal flow on each arc in turn, according to that order, yields a feasible solution. We characterize those transportation graphs for which there exists a single order which is good for all feasible problems with the same graph. The characterizations are shown to be intimately related to Monge sequences and to totally balanced matrices. We describe efficient algorithms which, for a given graph, construct such order whenever it exists. For a transportation problem with corresponding m×n bipartite graph with e arcs, we show how to generate such an order in O(min(e log e,mn)) steps. Using that order, the feasibility question for any given supply and demand vectors can be determined in O(m+n) time. We also extend the characterization and algorithms to general minimum cost flow problems in which the underlying graph is nonbipartite, and the sources and destinations are not predetermined. We generalize the theory of Monge sequences too to such problems. © 1993.