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
Algorithmica
Paper
Algorithms and complexity analysis for some flow problems
Abstract
Several network-flow problems with additional constraints are considered. They are all special cases of the linear-programming problem and are shown to be ℘-complete. It is shown that the existence of a strongly polynomial-time algorithm for any of these problems implies the existence of such an algorithm for the general linear-programming problem. On the positive side, strongly polynomial algorithms for some parametric flow problems are given, when the number of parameters is fixed. These algorithms are applicable to constrained flow problems when the number of additional constraints is fixed. © 1994 Springer-Verlag New York Inc.