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

Archive Staff Only: edit this record