A polyhedral study of the maximum edge subgraph problem

DOI10.1016/J.DAM.2011.10.011MaRDI QIDQ5916096zbMATH OpenOpenAlexFDO

Authors Flavia Bonomo, Javier Marenco, Daniela Saban, N. E. Stier-Moses

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 combinatoricsmaximum edge subgraph problemquasi-cliques

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Integer programming (90C10)

Recommendations

• A polyhedral study of the maximum edge subgraph problem
• Combinatorial properties and further facets of maximum edge subgraph polytopes
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Clique relaxations in social network analysis: the maximum \(k\)-plex problem
• Algorithms for the maximum k-club problem in graphs

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1168330 (Why is no real title available?)
• scientific article; zbMATH DE number 939919 (Why is no real title available?)
• scientific article; zbMATH DE number 1424314 (Why is no real title available?)
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• A polyhedral study of the generalized vertex packing problem
• A polyhedral study of the maximum edge subgraph problem
• Cardinality constrained Boolean quadratic polytope
• Clustering and domination in perfect graphs
• Complexity of finding dense subgraphs
• Different Formulations for Solving the HeaviestK-Subgraph Problem
• Emergence of Scaling in Random Networks
• Greedily Finding a Dense Subgraph
• Maximum matching and a polyhedron with 0,1-vertices
• Min-cut clustering
• Paths, Trees, and Flowers
• Statistical mechanics of complex networks
• The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The dense \(k\)-subgraph problem
• The densest \(k\)-subgraph problem on clique graphs
• Weighted k‐cardinality trees: Complexity and polyhedral structure

Cited in

(9)

• Polyhedral study of the connected subgraph problem
• Exact and heuristic algorithms for the weighted total domination problem
• scientific article; zbMATH DE number 2186837 (Why is no real title available?)
• A hybrid metaheuristic for the maximum \(k\)-plex problem
• Combinatorial algorithms for the maximum \(k\)-plex problem
• The sparse sequences of graphs
• Polyhedra of the Equivalent Subgraph Problem and Some Edge Connectivity Problems
• Combinatorial properties and further facets of maximum edge subgraph polytopes
• A polyhedral study of the maximum edge subgraph problem

Describes a project that uses

Uses Software

• NetworkX
• ABACUS
• SciPy
• DIMACS

This page was built for publication: A polyhedral study of the maximum edge subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5916096)