Some new classes of facets for the equicut polytope

DOI10.1016/0166-218X(94)00151-3zbMATH Open0838.90132MaRDI QIDQ1900144FDOQ1900144

Authors: Monique Laurent, Cid Carvalho de Souza 

Publication date: 30 May 1996

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

Recommendations

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

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)

Cites Work

• An Efficient Heuristic Procedure for Partitioning Graphs
• Title not available (Why is that?)
• On the cut polytope
• 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
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• The inequicut cone
• Lifting facets of the cut polytope
• A polynomial characterization of some graph partitioning problems

Cited In (19)

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

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)