### The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation

### Abstract

Let G = ( V, E ) be a undirected k-edge connected graph with weights ce on edges and wv on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-defining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable. Â© 2006 Elsevier Ltd. All rights reserved.

### Más información

Título según WOS: | The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation |

Título según SCOPUS: | The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation |

Título de la Revista: | DISCRETE OPTIMIZATION |

Volumen: | 3 |

Número: | 2 |

Editorial: | ELSEVIER SCIENCE BV |

Fecha de publicación: | 2006 |

Página de inicio: | 123 |

Página final: | 135 |

Idioma: | English |

URL: | http://linkinghub.elsevier.com/retrieve/pii/S1572528606000156 |

DOI: |
10.1016/j.disopt.2005.08.010 |

Notas: | ISI, SCOPUS |