Artículo
A polyhedral study of the maximum edge subgraph problem
Fecha de publicación:
09/2012
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
The study of cohesive subgroups is an important aspect of social network analysis. Cohesive subgroups are studied using different relaxations of the notion of clique in a graph. For instance, given a graph and an integer k, the maximum edge subgraph problem consists of finding a k-vertex subset such that the number of edges within the subset is maximum. This work proposes a polyhedral approach for this NP-hard problem. We study the polytope associated to an integer programming formulation of the problem, present several families of facet-inducing valid inequalities, and discuss the separation problem associated to these families. Finally, we implement a branch and cut algorithm for this problem. This computational study illustrates the effectiveness of the classes of inequalities presented in this work.
Palabras clave:
MAXIMUM EDGE SUBGRAPH PROBLEM
,
POLYHEDRAL COMBINATORICS
,
QUASI-CLIQUES
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(IMAS)
Articulos de INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Articulos de INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Citación
Bonomo, Flavia; Marenco, Javier Leonardo; Sabán, Daniela Hilén; Stier Moses, Nicolás; A polyhedral study of the maximum edge subgraph problem; Elsevier Science; Discrete Applied Mathematics; 160; 18; 9-2012; 2573-2590
Compartir
Altmétricas