Facets of the clique partitioning polytope

DOI10.1007/BF01580870zbMath0715.90092MaRDI QIDQ752015

Martin Grötschel, Yoshiko Wakabayashi

Publication date: 1990

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580870

zbMATH Keywords

edge weighted graph; clique partitioning

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

52B12: Special polytopes (linear programming, centrally symmetric, etc.)

90C27: Combinatorial optimization

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

Related Items

The clique partitioning problem: Facets and patching facets, Detecting critical node structures on graphs: A mathematical programming approach, Transitive packing, Good Clusterings Have Large Volume, The Branch and Cut Method for the Clique Partitioning Problem, Toward Optimal Community Detection: From Trees to General Weighted Networks, Improved Computational Approaches and Heuristics for Zero Forcing, The interval order polytope of a digraph, A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation, Selected Topics in Critical Element Detection, Using Mathematical Programming to Refine Heuristic Solutions for Network Clustering, Disconnecting graphs by removing vertices: a polyhedral approach, A Lagrangian relaxation approach to the edge-weighted clique problem, Efficient joint object matching via linear programming, A strong formulation for the graph partition problem, Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem, Derivations of large classes of facet defining inequalities of the weak order polytope using ranking structures, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, Fixed set search applied to the clique partitioning problem, Efficient enumeration of the optimal solutions to the correlation clustering problem, A three-phased local search approach for the clique partitioning problem, An extended edge-representative formulation for the \(K\)-partitioning problem, Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, A branch-and-bound algorithm for the acyclic partitioning problem, The corridor allocation problem, Fractional programming formulation for the vertex coloring problem, Improving heuristics for network modularity maximization using an exact algorithm, Orbitopal fixing, Column generation bounds for numerical microaggregation, Size-constrained graph partitioning polytopes, Binary positive semidefinite matrices and associated integer polytopes, A branch-and-cut algorithm for the partitioning-hub location-routing problem, Solving group technology problems via clique partitioning, Community detection with the weighted parsimony criterion, Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem, The Boolean quadratic polytope: Some characteristics, facets and relatives, A cutting plane algorithm for a clustering problem, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Facets for the cut cone. I, Cliques and clustering: A combinatorial approach, Lifting theorems and facet characterization for a class of clique partitioning inequalities, Min-cut clustering, Cluster analysis and mathematical programming, Solving the anti-covering location problem using Lagrangian relaxation, Reformulated acyclic partitioning for rail-rail containers transshipment, A two-level graph partitioning problem arising in mobile wireless communications, Projection results for the \(k\)-partition problem, Clustering data that are graph connected, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, Formulations and valid inequalities of the node capacitated graph partitioning problem, Facets of the \(k\)-partition polytope, On the partial order polytope of a digraph, Optimal solutions for the double row layout problem, The biclique partitioning polytope, Political districting to minimize cut edges, Multi-attribute community detection in international trade network, An overview of graph covering and partitioning, Facets from gadgets, Conference scheduling: a clustering-based approach, Max-multiflow/min-multicut for G+H series-parallel, Exact algorithms for the minimum \(s\)-club partitioning problem, Solving partitioning-hub location-routing problem using DCA, Flight gate assignment and recovery strategies with stochastic arrival and departure times, The realization problem for tail correlation functions, The partition problem, Detecting community structure: from parsimony to weighted parsimony, New bounds and constraint propagation techniques for the clique partitioning problem, Facet-defining inequalities for the simple graph partitioning polytope, Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, Multiprocessor scheduling under precedence constraints: polyhedral results, Clustering of microarray data via clique partitioning, A polyhedral study of lifted multicuts, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, Models for machine-part grouping in cellular manufacturing

Cites Work

• Ein Subgradientenverfahren zur Klassifikation qualitativer Daten
• A cutting plane algorithm for a clustering problem
• The median procedure in cluster analysis and social choice theory
• On Linear Characterizations of Combinatorial Optimization Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item