Facets of the clique partitioning polytope

DOI10.1007/BF01580870zbMATH Open0715.90092OpenAlexW2047893320MaRDI QIDQ752015FDOQ752015

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 graphclique partitioning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The median procedure in cluster analysis and social choice theory
• A cutting plane algorithm for a clustering problem
• On Linear Characterizations of Combinatorial Optimization Problems
• Ein Subgradientenverfahren zur Klassifikation qualitativer Daten
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (80)

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

This page was built for publication: Facets of the clique partitioning polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q752015)