The authors consider the problem of finding maximal flows with respect to capacities which are linear functions of a parameter t∈[0,T]. Since this problem is a special case of a parametric linear program the classic horizontal approach can be applied in which optimal solutions are computed for successive subintervals of [0,T]. The authors discuss an alternative algorithm which approximates in each iteration the optimal solution for all t∈[0,T]. This vertical algorithm is a labeling type algorithm where the flow variables are piecewise linear function. Flow augmentations are done along conditional flow augmenting paths which can be found by modified path algorithms. The vertical algotithm can be used to solve the parametric flow problem optimally as well as to compute a good approximation for all t if the computation of the optimal solution turns out to be too time consuming.
