Network Reinforcement

Francisco Barahona (barahonus.ibm.com)

Abstract: We give an algorithm for the following problem: given a graph $G=(V,E)$ with edge-weights and a nonnegative integer $k$, find a minimum cost set of edges that contains $k$ disjoint spanning trees. This also solves the following {\it reinforcement problem}: given a network, a number $k$ and a set of candidate edges, each of them with an associated cost, find a minimum cost set of candidate edges to be added to the network so it contains $k$ disjoint spanning trees. The number $k$ is seen as a measure of the invulnerability of a network. We show that this can be solved with $|V|$ applications of the minimum cut algorithm of Goldberg \& Tarjan.

Keywords: spanning trees

Category 1: Combinatorial Optimization (Graphs and Matroids )

Citation:

Download: [PDF]

Entry Submitted: 09/25/2003
Entry Accepted: 09/26/2003
Entry Last Modified: 03/09/2006

Modify/Update this entry