A fast algorithm for the generalized parametric minimum cut problem and applications (Q1186785)

Many combinatorial optimization problems are solved by a sequence of network flow computations on a network whose edge capacities are given as a function of a parameter \(\lambda\). Recently Gallo et al. showed that for an important class of networks, called monotone parametric flow networks, a sequence of \(O(n)\) flow computations could be solved in the same worst-case time bound as a single flow. However, these results require one of two special assumptions: either that the \(\lambda\) values are presented in increasing or decreasing order; or that the edge capacity functions are affine functions of \(\lambda\). This paper shows how to remove both of these assumptions while obtaining the same running times.