Compacting cuts. A new linear formulation for minimum cut

DOI10.1145/1541885.1541888MaRDI QIDQ6486921zbMATH OpenOpenAlexWikidataFDO

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

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1541885.1541888

zbMATH Keywords

complexitylinear programming formulationminimum cut problem

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Integer programming (90C10)

Recommendations

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

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 Q6486921)