|
|
|
 |
|
Vladimir Kolmogorov
Adastral Park, UCL, UK
Wednesday 20 February 2008
16.00
Seminar Room B10 (Basement)
Alexandra House, 17 Queen Square, London, WC1N 3AR
A faster algorithm for computing the principal sequence of partitions of a graph
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 G=(V,E,c) with 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.