Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables

DOI10.1016/j.dam.2016.04.002zbMath1348.05160OpenAlexW2346810955MaRDI QIDQ335322

Arnaud Knippel, Zacharie Ales, Alexandre Pauchet

Publication date: 2 November 2016

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

Full work available at URL: https://doi.org/10.1016/j.dam.2016.04.002

zbMATH Keywords

combinatorial optimizationgraph partitioningpolyhedral approach

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (11)

An overview of graph covering and partitioning ⋮ Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables ⋮ A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph ⋮ A modeling and computational study of the frustration index in signed networks ⋮ The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp> ⋮ Efficient enumeration of the optimal solutions to the correlation clustering problem ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ The sport teams grouping problem ⋮ A two-level graph partitioning problem arising in mobile wireless communications ⋮ Improved compact formulations for a wide class of graph partitioning problems in sparse graphs ⋮ Integer programming formulations and efficient local search for relaxed correlation clustering

Cites Work

• Unnamed Item
• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• Orbitopal fixing
• Size-constrained graph partitioning polytopes
• Facets of the clique partitioning polytope
• A cutting plane algorithm for a clustering problem
• Some simplified NP-complete graph problems
• The node capacitated graph partitioning problem: A computational study
• Lifting theorems and facet characterization for a class of clique partitioning inequalities
• Min-cut clustering
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• On the partial order polytope of a digraph
• An exact algorithm for graph partitioning
• Linear and quadratic programming approaches for the general graph partitioning problem
• The partition problem
• Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
• On the asymmetric representatives formulation for the vertex coloring problem
• The equipartition polytope. I: Formulations, dimension and basic facets
• On the Solution of a Graph Partitioning Problem under Capacity Constraints
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• An Efficient Heuristic Procedure for Partitioning Graphs
• Realignment in the National Football League: Did they do it right?
• The clique partitioning problem: Facets and patching facets
• On the cut polytope

This page was built for publication: Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables