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
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
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v160_n18_p2573_Bonomo_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-paper_0166218X_v160_n18_p2573_Bonomo_oai
record_format dspace
spelling I28-R145-paper_0166218X_v160_n18_p2573_Bonomo_oai2024-08-16 Bonomo, F. Marenco, J. Saban, D. Stier-Moses, N.E. 2012 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. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2573_Bonomo info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2012;160(18):2573-2590 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 A polyhedral study of the maximum edge subgraph problem info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v160_n18_p2573_Bonomo_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
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
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v160_n18_p2573_Bonomo_oai
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_ 1809357091215769600

Ejemplares similares