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

Kolmogorov V. 2010. A faster algorithm for computing the principal sequence of partitions of a graph. Algorithmica. 56(4), 394–412.

Download

**No fulltext has been uploaded. References only!**

*Journal Article*|

*Published*

Author

Abstract

We consider the following problem: given an undirected weighted graph G = (V,E,c) with nonnegative weights, minimize function c(δ(Π))- λ|Π| for all values of parameter λ. Here Π 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 |Π| 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| 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.

Publishing Year

Date Published

2010-04-01

Journal Title

Algorithmica

Volume

56

Issue

4

Page

394 - 412

IST-REx-ID

### Cite this

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

*Algorithmica*. 2010;56(4):394-412. doi:10.1007/s00453-008-9177-zKolmogorov, V. (2010). A faster algorithm for computing the principal sequence of partitions of a graph.

*Algorithmica*. Springer. https://doi.org/10.1007/s00453-008-9177-zKolmogorov, Vladimir. “A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph.”

*Algorithmica*. Springer, 2010. https://doi.org/10.1007/s00453-008-9177-z.V. Kolmogorov, “A faster algorithm for computing the principal sequence of partitions of a graph,”

*Algorithmica*, vol. 56, no. 4. Springer, pp. 394–412, 2010.Kolmogorov, Vladimir. “A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph.”

*Algorithmica*, vol. 56, no. 4, Springer, 2010, pp. 394–412, doi:10.1007/s00453-008-9177-z.