A polyhedral study of the maximum edge subgraph problem

DOI10.1016/j.dam.2011.10.011zbMath1262.90178MaRDI QIDQ5916096

Flavia Bonomo-Braberman, Javier Marenco, Nicolás E. Stier-Moses, Daniela Saban

Publication date: 22 November 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.011

zbMATH Keywords

polyhedral combinatorics; maximum edge subgraph problem; quasi-cliques

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

91D30: Social networks; opinion dynamics

05C35: Extremal problems in graph theory

05C82: Small world graphs, complex networks (graph-theoretic aspects)

90C10: Integer programming

Uses Software

• NetworkX
• ABACUS
• SciPy
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• Clustering and domination in perfect graphs
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Min-cut clustering
• Cardinality constrained Boolean quadratic polytope
• Complexity of finding dense subgraphs
• The densest \(k\)-subgraph problem on clique graphs
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• A polyhedral study of the generalized vertex packing problem
• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Greedily Finding a Dense Subgraph
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• A polyhedral study of the maximum edge subgraph problem
• The dense \(k\)-subgraph problem
• Different Formulations for Solving the HeaviestK-Subgraph Problem