Mostrar el registro sencillo del ítem
dc.contributor.author
Bonomo, Flavia
dc.contributor.author
Marenco, Javier Leonardo
dc.contributor.author
Sabán, Daniela Hilén
dc.contributor.author
Stier Moses, Nicolás
dc.date.available
2022-08-25T02:22:14Z
dc.date.issued
2012-09
dc.identifier.citation
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
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/166513
dc.description.abstract
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.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.subject
MAXIMUM EDGE SUBGRAPH PROBLEM
dc.subject
POLYHEDRAL COMBINATORICS
dc.subject
QUASI-CLIQUES
dc.subject.classification
Matemática Aplicada
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.subject.classification
Ciencias de la Computación
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
A polyhedral study of the maximum edge subgraph problem
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2022-05-04T17:17:23Z
dc.journal.volume
160
dc.journal.number
18
dc.journal.pagination
2573-2590
dc.journal.pais
Estados Unidos
dc.journal.ciudad
New York
dc.description.fil
Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Marenco, Javier Leonardo. Universidad Nacional de General Sarmiento; Argentina
dc.description.fil
Fil: Sabán, Daniela Hilén. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Universidad Nacional de General Sarmiento; Argentina
dc.description.fil
Fil: Stier Moses, Nicolás. Columbia University; Estados Unidos
dc.journal.title
Discrete Applied Mathematics
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2011.10.011
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X11003702
Archivos asociados