Paper Info
Title
A polyhedral study of the maximum edge subgraph problem
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.
Year
DOI
Venue
2009
10.1016/j.endm.2009.11.033
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
polyhedral combinatorics,maximum edge subgraph problem,social network analysis
Integer,Discrete mathematics,Combinatorics,Maximum common subgraph isomorphism problem,Vertex (geometry),Clique,Induced subgraph isomorphism problem,Integer programming,Subgraph isomorphism problem,Mathematics,Polyhedral combinatorics
Journal
Volume
Issue
ISSN
35
18
Electronic Notes in Discrete Mathematics
Citations 
PageRank 
References 
1
0.43
13
Authors
4
Name
Order
Citations
PageRank
Flavia Bonomo122628.95
Javier Marenco26919.51
Daniela Saban3317.84
Nicolas E. Stier-Moses4315.11