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

DOI10.1016/j.dam.2016.04.002zbMath1348.05160MaRDI 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 optimization; graph partitioning; polyhedral approach

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C22: Signed and weighted graphs

Related Items

Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, 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, A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph

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