Premium
A branch‐and‐cut algorithm for the k ‐edge connected subgraph problem
Author(s) -
Bendali F.,
Diarrassouba I.,
Mahjoub A.R.,
Didi Biha M.,
Mailfert J.
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20310
Subject(s) - polytope , branch and cut , preprocessor , enhanced data rates for gsm evolution , algorithm , vertex connectivity , reduction (mathematics) , mathematics , facet (psychology) , combinatorics , computer science , integer programming , graph , artificial intelligence , geometry , psychology , social psychology , personality , vertex (graph theory) , big five personality traits
In this article, we consider the k ‐edge connected subgraph problem from a polyhedral point of view. We introduce further classes of valid inequalities for the associated polytope and describe sufficient conditions for these inequalities to be facet defining. We also devise separation routines for these inequalities and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we develop a Branch‐and‐Cut algorithm and present some computational results. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010