On the Graph Bisection Cut Polytope

DOI10.1137/060675253MaRDI QIDQ3394988zbMATH OpenOpenAlexFDO

Authors Michael Armbruster, Christoph Helmberg, Marzena Fügenschuh, Alexander Martin

Publication date 20 August 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/060675253

zbMATH Keywords

graph partitioninginteger polyhedravalid inequalities

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• scientific article; zbMATH DE number 5237020
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• scientific article; zbMATH DE number 1333614
• The partition problem
• Some new classes of facets for the equicut polytope

Cited in

(16)

• Separating subdivision of bicycle wheel inequalities over cut polytopes
• Graph bisection revisited
• Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes
• \(b\)-tree facets for the simple graph partitioning polytope
• An overview of graph covering and partitioning
• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• Polyhedral results for the bipartite induced subgraph problem
• Generating facets for the cut polytope of a graph by triangular elimination
• On generalized bisection of 𝑛-simplices
• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• On the polyhedral structure of uniform cut polytopes
• scientific article; zbMATH DE number 1905103 (Why is no real title available?)
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• From equipartition to uniform cut polytopes: extended polyhedral results
• On the relative strength of split, triangle and quadrilateral cuts
• SCIP: solving constraint integer programs

This page was built for publication: On the Graph Bisection Cut Polytope

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