Algorithms for flows with parametric capacities

We consider the problem of finding maximal flows with respect to capacities which are linear functions of a parametert 0,T]. Since this problem is a special case of a parametric linear program the classichorizontal approach can be applied in which optimal solutions are computed for successive subintervals of 0,T]. We discuss an alternative algorithm which approximates in each iteration the optimal solution for allt 0,T]. Thisvertical algorithm is a labeling type algorithm where the flow variables are piecewise linear functions. Flow augmentations are done alongconditional flow augmenting paths which can be found by modified path algorithms. The vertical algorithm can be used to solve the parametric flow problem optimally as well as to compute a good approximation for allt if the computation of the optimal solution turns out to be too time consuming.Partially supported by NSF Grants ECS-8412926 and INT-8521433, and NATO Grant RG 85/0240.