Some new classes of facets for the equicut polytope

DOI10.1016/0166-218X(94)00151-3zbMath0838.90132MaRDI QIDQ1900144

Monique Laurent, Cid Carvalho De Souza

Publication date: 30 May 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

equicut polytopeminimum weight equicut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27) Graph theory (05C99)

Related Items

Application of cut polyhedra. I, An overview of graph covering and partitioning, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, A branch-and-cut algorithm for the equicut problem, On the polyhedral structure of uniform cut polytopes, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem, Facet-defining inequalities for the simple graph partitioning polytope, Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes, From equipartition to uniform cut polytopes: extended polyhedral results, Formulations and valid inequalities of the node capacitated graph partitioning problem, The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations, Engineering Branch-and-Cut Algorithms for the Equicut Problem

Cites Work

• Unnamed Item
• The inequicut cone
• Lifting facets of the cut polytope
• A polynomial characterization of some graph partitioning problems
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• An Efficient Heuristic Procedure for Partitioning Graphs
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• On the cut polytope