Some new classes of facets for the equicut polytope
From MaRDI portal
Publication:1900144
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)
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
