A polyhedral study of the maximum edge subgraph problem

DOI10.1016/J.ENDM.2009.11.033zbMATH Open1268.90112OpenAlexW2180803756MaRDI QIDQ5891092FDOQ5891092

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

Publication date 19 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2573_Bonomo

zbMATH Keywords

polyhedral combinatoricsmaximum edge subgraph problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10) Social networks; opinion dynamics (91D30) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A polyhedral study of the maximum edge subgraph problem
• The maximum common edge subgraph problem: A polyhedral investigation
• Combinatorial properties and further facets of maximum edge subgraph polytopes
• Polyhedral study of the maximum common induced subgraph problem
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• Polyhedral study of the connected subgraph problem
• The approximation of maximum subgraph problems
• On the complexity of the maximum subgraph problem
• Polyhedra of the Equivalent Subgraph Problem and Some Edge Connectivity Problems
• Optimal connected subgraphs: Integer programming formulations and polyhedra

Cites work

• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• Complexity of finding dense subgraphs
• Different Formulations for Solving the HeaviestK-Subgraph Problem
• Greedily Finding a Dense Subgraph
• The dense \(k\)-subgraph problem

Cited in

(6)

• Polyhedral study of the connected subgraph problem
• scientific article; zbMATH DE number 2186837 (Why is no real title available?)
• Compressing strongly connected subgroups in social networks: an entropy-based approach
• The cohesiveness of subgroups in social networks: A view from game theory
• Combinatorial properties and further facets of maximum edge subgraph polytopes
• A polyhedral study of the maximum edge subgraph problem

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 Q5891092)