A polyhedral study of the maximum edge subgraph problem

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Marenco, J., Saban, D., Stier-Moses, N.E.
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: 2012
Materias:
Maximum edge subgraph problem
Polyhedral combinatorics
Quasi-cliques
Branch-and-cut algorithms
Computational studies
Integer programming formulations
Polyhedral approach
Polyhedral studies
Polytopes
Separation problems
Social Network Analysis
Subgraph problems
Valid inequality
Integer programming
Linear programming
Social networking (online)
Computational complexity
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2573_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paperaa:paper_0166218X_v160_n18_p2573_Bonomo
record_format dspace
spelling paperaa:paper_0166218X_v160_n18_p2573_Bonomo2023-06-12T16:46:55Z A polyhedral study of the maximum edge subgraph problem Discrete Appl Math 2012;160(18):2573-2590 Bonomo, F. Marenco, J. Saban, D. Stier-Moses, N.E. Maximum edge subgraph problem Polyhedral combinatorics Quasi-cliques Branch-and-cut algorithms Computational studies Integer programming formulations Polyhedral approach Polyhedral combinatorics Polyhedral studies Polytopes Quasi-cliques Separation problems Social Network Analysis Subgraph problems Valid inequality Integer programming Linear programming Social networking (online) Computational complexity 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. © 2011 Elsevier B.V. All rights reserved. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Saban, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Stier-Moses, N.E. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2012 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2573_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv eng
topic Maximum edge subgraph problem
Polyhedral combinatorics
Quasi-cliques
Branch-and-cut algorithms
Computational studies
Integer programming formulations
Polyhedral approach
Polyhedral combinatorics
Polyhedral studies
Polytopes
Quasi-cliques
Separation problems
Social Network Analysis
Subgraph problems
Valid inequality
Integer programming
Linear programming
Social networking (online)
Computational complexity
spellingShingle Maximum edge subgraph problem
Polyhedral combinatorics
Quasi-cliques
Branch-and-cut algorithms
Computational studies
Integer programming formulations
Polyhedral approach
Polyhedral combinatorics
Polyhedral studies
Polytopes
Quasi-cliques
Separation problems
Social Network Analysis
Subgraph problems
Valid inequality
Integer programming
Linear programming
Social networking (online)
Computational complexity
Bonomo, F.
Marenco, J.
Saban, D.
Stier-Moses, N.E.
A polyhedral study of the maximum edge subgraph problem
topic_facet Maximum edge subgraph problem
Polyhedral combinatorics
Quasi-cliques
Branch-and-cut algorithms
Computational studies
Integer programming formulations
Polyhedral approach
Polyhedral combinatorics
Polyhedral studies
Polytopes
Quasi-cliques
Separation problems
Social Network Analysis
Subgraph problems
Valid inequality
Integer programming
Linear programming
Social networking (online)
Computational complexity
description 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. © 2011 Elsevier B.V. All rights reserved.
format Artículo
Artículo
publishedVersion
author Bonomo, F.
Marenco, J.
Saban, D.
Stier-Moses, N.E.
author_facet Bonomo, F.
Marenco, J.
Saban, D.
Stier-Moses, N.E.
author_sort Bonomo, F.
title A polyhedral study of the maximum edge subgraph problem
title_short A polyhedral study of the maximum edge subgraph problem
title_full A polyhedral study of the maximum edge subgraph problem
title_fullStr A polyhedral study of the maximum edge subgraph problem
title_full_unstemmed A polyhedral study of the maximum edge subgraph problem
title_sort polyhedral study of the maximum edge subgraph problem
publishDate 2012
url http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2573_Bonomo
work_keys_str_mv AT bonomof apolyhedralstudyofthemaximumedgesubgraphproblem
AT marencoj apolyhedralstudyofthemaximumedgesubgraphproblem
AT saband apolyhedralstudyofthemaximumedgesubgraphproblem
AT stiermosesne apolyhedralstudyofthemaximumedgesubgraphproblem
AT bonomof polyhedralstudyofthemaximumedgesubgraphproblem
AT marencoj polyhedralstudyofthemaximumedgesubgraphproblem
AT saband polyhedralstudyofthemaximumedgesubgraphproblem
AT stiermosesne polyhedralstudyofthemaximumedgesubgraphproblem
_version_ 1769810285230555136

Ejemplares similares