Reduced-size formulations for metric and cut polyhedra in sparse graphs

DOI10.1002/NET.21723MaRDI QIDQ4565778zbMATHOpenAlexFDO

Authors Viet Hung Nguyen, Michel Minoux, Dang Phuong Nguyen

Publication date 13 June 2018

Published in Networks (Search for Journal in Brave)

Full work available at URL https://hal.sorbonne-universite.fr/hal-01405725/file/Nguyen_2016_Reduced-size.pdf

zbMATH Keywords

series-parallel graphextended formulationtriangle inequalitiessparse graphmax-cut problemmetric polyhedral

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42)

Recommendations

• Improved compact formulations for metric and cut polyhedra
• scientific article; zbMATH DE number 665696
• Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
• An effective compact formulation of the max cut problem on sparse graphs
• Improved compact formulations for a wide class of graph partitioning problems in sparse graphs

Cited in

(3)

• Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
• scientific article; zbMATH DE number 665696 (Why is no real title available?)
• Improved compact formulations for metric and cut polyhedra

This page was built for publication: Reduced-size formulations for metric and cut polyhedra in sparse graphs

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