An extended edge-representative formulation for the \(K\)-partitioning problem

DOI10.1016/j.endm.2016.03.044zbMath1351.90035OpenAlexW2395781967MaRDI QIDQ325479

Zacharie Ales, Arnaud Knippel

Publication date: 18 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2016.03.044

zbMATH Keywords

branch-and-cut algorithmcombinatorial optimizationgraph partitioningpolyhedral approach

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10)

Related Items (3)

Computational study of a branching algorithm for the maximum \(k\)-cut problem ⋮ The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp> ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints

Cites Work

• Orbitopal fixing
• Robust optimization of graph partitioning involving interval uncertainty
• Size-constrained graph partitioning polytopes
• A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
• 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
• An exact algorithm for graph partitioning
• The partition problem
• Facet-defining inequalities for the simple graph partitioning polytope
• On the asymmetric representatives formulation for the vertex coloring problem
• On the Solution of a Graph Partitioning Problem under Capacity Constraints
• On Finding Dense Subgraphs
• Clique-Web Facets for Multicut Polytopes
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The clique partitioning problem: Facets and patching facets
• On the cut polytope

This page was built for publication: An extended edge-representative formulation for the \(K\)-partitioning problem