A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph |
| |
Authors: | Vladimir Kolmogorov |
| |
Affiliation: | 1. Adastral Park Campus, University College London, Adastral Park, Martlesham Heath, IP5 3RE, UK
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|