UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

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. 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
URI: http://discovery.ucl.ac.uk/id/eprint/123730
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item