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-z
Kolmogorov, 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-z
Kolmogorov, 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 V. 2010. A faster algorithm for computing the principal sequence of partitions of a graph. Algorithmica. 56(4), 394–412.
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.
Google Scholar