A polyhedral study of the maximum edge subgraph problem

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

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

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

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

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Polyhedral study of the connected subgraph problem
• A polyhedral study of the maximum edge subgraph problem
• Combinatorial properties and further facets of maximum edge subgraph polytopes

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)