ALGORITHMS AND COMPLEXITY ANALYSIS FOR SOME FLOW PROBLEMS

Several network-flow problems with additional constraints are consider ed. They are all special cases of the linear-programming problem and a re shown to be P-complete. It is shown that the existence of a strongl y polynomial-time algorithm for any of these problems implies the exis tence of such an algorithm for the general linear-programming problem. On the positive side, strongly polynomial algorithms for some paramet ric flow problems are given, when the number of parameters is fixed. T hese algorithms are applicable to constrained flow problems when the n umber of additional constraints is fixed.