An effective compact formulation of the max cut problem on sparse graphs

DOI10.1016/J.ENDM.2011.05.020zbMATH Open1268.05204OpenAlexW1994813942MaRDI QIDQ2840693FDOQ2840693

Authors: Giuseppe Lancia, Paolo Serafini 

Publication date: 23 July 2013

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

Full work available at URL: https://doi.org/10.1016/j.endm.2011.05.020

Recommendations

• An exact algorithm for MAX-CUT in sparse graphs
• A mixed integer model for the sparsest cut problem
• A novel formulation of the max-cut problem and related algorithm
• Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
• Improved compact formulations for a wide class of graph partitioning problems in sparse graphs

zbMATH Keywords

max cut problemintersecting cuts and circuitsodd circuits. sparse graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Encyclopedia of Algorithms
• Title not available (Why is that?)
• Using separation algorithms to generate mixed integer model reformulations
• Experiments in quadratic 0-1 programming
• Compact vs. exponential-size LP relaxations
• Compact optimization can outperform separation: a case study in structural proteomics

Cited In (6)

• A mixed integer model for the sparsest cut problem
• Local search inequalities
• Improved compact formulations for metric and cut polyhedra
• Deriving compact extended formulations via LP-based separation techniques
• An extended formulation for the 1‐wheel inequalities of the stable set polytope
• Deriving compact extended formulations via LP-based separation techniques

This page was built for publication: An effective compact formulation of the max cut problem on sparse graphs

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