Some new classes of facets for the equicut polytope

DOI10.1016/0166-218X(94)00151-3MaRDI QIDQ1900144zbMATH OpenFDO

Authors 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) Combinatorial optimization (90C27) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Graph theory (05C99)

Recommendations

• On the cut polytope
• The inequicut cone
• The equipartition polytope. I: Formulations, dimension and basic facets
• Facets for the cut cone. I

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A polynomial characterization of some graph partitioning problems
• An Efficient Heuristic Procedure for Partitioning Graphs
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• Lifting facets of the cut polytope
• On the cut polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• The inequicut cone

Cited in

(19)

• Facet-defining inequalities for the simple graph partitioning polytope
• On the polyhedral structure of uniform cut polytopes
• New facets for the planar subgraph polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• From equipartition to uniform cut polytopes: extended polyhedral results
• An overview of graph covering and partitioning
• scientific article; zbMATH DE number 1775539 (Why is no real title available?)
• On the Graph Bisection Cut Polytope
• The inequicut cone
• A branch-and-cut algorithm for the equicut problem
• The even and odd cut polytopes
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Application of cut polyhedra. I
• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• scientific article; zbMATH DE number 2068098 (Why is no real title available?)
• Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes
• Engineering branch-and-cut algorithms for the equicut problem

This page was built for publication: Some new classes of facets for the equicut polytope

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