Kolmogorov, V (2010) A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph. ALGORITHMICA , 56 (4) 394 - 412. 10.1007/s00453-008-9177-z.
Full text not available from this repository.
Abstract
We consider the following problem: given an undirected weighted graph G=(V,E,c) with nonnegative weights, minimize function c(delta(I ))-lambda|I | for all values of parameter lambda. Here I 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 |I | 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.
| Type: | Article |
|---|---|
| Title: | A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph |
| DOI: | 10.1007/s00453-008-9177-z |
| Keywords: | Principal sequence of partitions, Network attack, Network strength, Minimum cut/maximum flow, Parametric algorithm, PARAMETRIC MAXIMUM FLOW, NETWORK, REINFORCEMENT, POLYMATROIDS, STRENGTH, TREES |
| UCL classification: | UCL > School of BEAMS > Faculty of Engineering Science > Computer Science |
Archive Staff Only: edit this record