ISSN:
1432-0541
Keywords:
Parametric flow
;
Constrained flow
;
Strongly polynomial time
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01240739
