A FASTER PARAMETRIC MINIMUM-CUT ALGORITHM

Gallo et al. [4] 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 th at for an important class of networks, the k maximum flows and minimum cuts can be computed simply in O(n(3) + kn(2)) total time, provided t hat the capacity changes are made ''in order.'' Using dynamic trees th eir time bound is O(nm log(n(2)/m)+ km log(n(2)/m)). We show how to re duce the total time, using a simple algorithm, to O(n(3) + kn) for exp licitly computing the k minimum cuts and implicitly representing the k flows. Using dynamic trees our bound is O(nm log(n(2)/m)+ kn log(n2/m )). We further reduce the total time to O(n(2) root m) if k is at most O(n). We also apply the ideas from [10] to show that the faster bound s hold even when the capacity changes are not ''in order,'' provided w e only need the minimum cuts; if the flows are required then the times are respectively O(n(3) + km) and O(n(2) root m). We illustrate the u tility of these results by applying them to the rectilinear layout pro blem.