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.

## 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 UCL > School of BEAMS > Faculty of Engineering Science > Computer Science |

URI: | http://discovery.ucl.ac.uk/id/eprint/123730 |

### Archive Staff Only

View Item |