I will talk about an application of the maxflow algorithm to the problem of graph partitioning.
Consider the following problem: given an undirected weighted graph
nonnegative weights, minimize function c(P) - k*|P| for all values of parameter k. Here P is a partition of the set of nodes, c(P) is the cost of edges whose endpoints belong to different components of the partition, and |P| is the number of components. The current best known algorithm for this problem has complexity O(|V|^2) maximum flow computations.
I will present a method which improves it to |V| parametric maximum flow computations.