Title: Network Reinforcement


			Francisco Barahona 
			        IBM
			    PO Box 218, 
		    Yorktown Heights, NY 10598
		     Email: barahon@us.ibm.com
           Web: http://www.research.ibm.com/people/b/barahon/


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. The 
previously known algorithm requires solving $2|E|$ minimum cut problems.