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

DOI10.1016/J.DISOPT.2017.03.001MaRDI QIDQ1751235zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 17641
• Clique-Web Facets for Multicut Polytopes
• On the Graph Bisection Cut Polytope
• scientific article; zbMATH DE number 1079001
• Some new classes of facets for the equicut polytope

Cites work

• \(b\)-tree facets for the simple graph partitioning polytope
• An exact algorithm for graph partitioning
• Facet-defining inequalities for the simple graph partitioning polytope
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• scientific article; zbMATH DE number 3991298 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1175943 (Why is no real title available?)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• On the Graph Bisection Cut Polytope
• Size-constrained graph partitioning polytopes
• Some new classes of facets for the equicut polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• The node capacitated graph partitioning problem: A computational study

Cited in

(2)

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

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

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