We study the following NP-hard graph augmentation problem: Given a weighted graph G and a connected spanning subgraph H of G, find a minimum weight set of edges of G to be added to H so that H becomes 2-edge-connected. We provide a formulation of the problem as a set covering problem, and we analyze the conditions for which the linear programming relaxation of our formulation always gives an integer solution. This yields instances of the problem that can be solved in polynomial time. As we will show in the paper, these particular instances have not only theoretical but also practical interest, since they model a wide range of survivability problems in communication networks.
Edge-connectivity augmentation and network matrices
Galluccio A;Proietti G
2004
Abstract
We study the following NP-hard graph augmentation problem: Given a weighted graph G and a connected spanning subgraph H of G, find a minimum weight set of edges of G to be added to H so that H becomes 2-edge-connected. We provide a formulation of the problem as a set covering problem, and we analyze the conditions for which the linear programming relaxation of our formulation always gives an integer solution. This yields instances of the problem that can be solved in polynomial time. As we will show in the paper, these particular instances have not only theoretical but also practical interest, since they model a wide range of survivability problems in communication networks.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
