A faster parametric minimum-cut algorithm

Gallo et al recently examined the problem of computing on-line a sequence of k maximum flows and minimum cuts in a network of n nodes, where certain edge capacities change between each flow. They showed that for an important class of networks, the k maximum flows and minimum cuts can be computed simply in total time, provided that the capacity changes are made ‘in order’. Using dynamic trees their time bound is . The authors show how to reduce the total time, using a simple algorithm, to for explicitly computing the k minimum cuts and implicitly representing the k flows. Using dynamic trees the present bound is . The authors further reduce the total time to if k is at most O(n). They also show that the faster bounds hold even when the capacity changes are not ‘in order’, provided only the minimum cuts are needed; if the flows are required then the times are respectively and . The authors illustrate the utility of these results by applying them to the rectilinear layout problem.