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

DOI10.1002/NET.21723zbMATH Open1388.05106OpenAlexW2549223366MaRDI QIDQ4565778FDOQ4565778

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

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

zbMATH Keywords

series-parallel graphextended formulationtriangle inequalitiessparse graphmax-cut problemmetric polyhedral

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42)

Cited In (2)

• Title not available (Why is that?)
• Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results

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)