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

Vladimir Kolmogorov.

In Algorithmica, April 2010, 56(4):394-412.


We consider the following problem: given an undirected weighted graph $G=(V,E,c)$ with nonnegative weights, minimize function $c(\delta(\mathscr{A})) - \lambda |\mathscr{A}|$ for all values of parameter $\lambda$. Here $\mathscr{A}$ is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components of the partition, and $|\mathscr{A}|$ is the number of components. The current best known algorithm for this problem has complexity $O(|V|^2)$ maximum flow computations. We improve it to $|V|$ {\em parametric} maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good separator, e.g. for planar graphs.


doi link

Note: Certain claims about the parametric maxflow algorithm made in this paper will be reverted soon. Please check this page later.