Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes

DOI10.1016/j.disopt.2017.03.001zbMath1387.90228OpenAlexW2603934394MaRDI QIDQ1751235

Michael Malmros Sørensen

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://pure.au.dk/ws/files/111162267/PBC_facets.pdf

zbMATH Keywords

graph bisectiongraph partitioningpolyhedral combinatorics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

An overview of graph covering and partitioning ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Size-constrained graph partitioning polytopes
• The node capacitated graph partitioning problem: A computational study
• \(b\)-tree facets for the simple graph partitioning polytope
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Some new classes of facets for the equicut polytope
• An exact algorithm for graph partitioning
• Facet-defining inequalities for the simple graph partitioning polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• On the Graph Bisection Cut Polytope
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms

This page was built for publication: Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes