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