A linear programming approach to increasing the weight of all minimum spanning trees

Francisco Barahona (barahonus.ibm.com)
Mourad Baiou (baioucustsv.univ-bpclermont.fr)

Abstract: Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. We formulate this as a combinatorial linear program and give an algorithm.

Keywords: Minimum weight spanning trees, packing spanning trees, network reinforcement, strength problem

Category 1: Combinatorial Optimization (Graphs and Matroids )

Citation:

Download: [PDF]

Entry Submitted: 01/06/2005
Entry Accepted: 01/06/2005
Entry Last Modified: 03/09/2006

Modify/Update this entry