New bounds and constraint propagation techniques for the clique partitioning problem

DOI10.1016/j.dam.2013.02.011zbMath1287.68155OpenAlexW1986827871MaRDI QIDQ2446845

Florian Jaehn, Erwin Pesch

Publication date: 22 April 2014

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

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

zbMATH Keywords

branch and boundconstraint propagationclique partitioning

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Flight gate assignment and recovery strategies with stochastic arrival and departure times ⋮ An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment ⋮ A three-phased local search approach for the clique partitioning problem ⋮ A branch-and-bound algorithm for the acyclic partitioning problem ⋮ Grouping products for the optimization of production processes: a case in the steel manufacturing industry ⋮ Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem ⋮ Fixed set search applied to the clique partitioning problem ⋮ Reformulated acyclic partitioning for rail-rail containers transshipment ⋮ Clustering data that are graph connected ⋮ Lagrangian relaxation and pegging test for the clique partitioning problem ⋮ The biclique partitioning polytope ⋮ Balanced Partition of a Graph for Football Team Realignment in Ecuador

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Facets of the clique partitioning polytope
• Solving group technology problems via clique partitioning
• Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem
• On the complexity of partitioning graphs into connected subgraphs
• A cutting plane algorithm for a clustering problem
• Cliques and clustering: A combinatorial approach
• Min-cut clustering
• The partition problem
• Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
• Clustering of microarray data via clique partitioning
• The NP-Completeness of Edge-Coloring
• Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and Complexity
• Fast Clustering Algorithms
• The clique partitioning problem: Facets and patching facets
• The Number of Partitions of a Set

This page was built for publication: New bounds and constraint propagation techniques for the clique partitioning problem