Compacting cuts, a new linear formulation for minimum cut

MaRDI QIDQ2934581zbMATH OpenFDO

Authors Goran Konjevod, Greg Little, Venkatesh Natarajan, Ojas Parekh, Robert D. Carr

Publication date 18 December 2014

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Compacting cuts. A new linear formulation for minimum cut
• Improved compact formulations for metric and cut polyhedra
• Compact representations of cuts
• Extended formulations in combinatorial optimization
• Extended formulations for the \(A\)-cut problem

Cited in

(8)

• The parsimonious property of cut covering problems and its applications
• On minimum cuts and the linear arrangement problem
• On the dominant of the \(s\)-\(t\)-cut polytope: vertices, facets, and adjacency
• Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
• Compact representations of cuts
• Extended formulations in combinatorial optimization
• Extended formulations in combinatorial optimization
• Compacting cuts. A new linear formulation for minimum cut

This page was built for publication: Compacting cuts, a new linear formulation for minimum cut

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