A faster algorithm for computing the principal sequence of partitions of a graph

Vladimir Kolmogorov
University College London

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.

Presentation (PowerPoint File)

Back to Graph Cuts and Related Discrete or Continuous Optimization Problems