A cutting-plane approach to the edge-weighted maximal clique problem
The following maximal clique problem is considered. Given a complete undirected graph \(G\) with real edge-weights, find a clique \(C\) in \(G\) such that the sum of edge-weights in \(C\) is maximal. It is shown that contrary to the fact that cutting planes algorithms have been successfully applied to related problems like the edge-weighted partition problem or the linear ordering problem similar methods applied to the maximal clique problem fails. A computational study shows that even for graphs with 15 or 25 vertices the results are very poor.
- An extended formulation approach to the edge-weighted maximal clique problem
- scientific article; zbMATH DE number 26478
- Complexity and heuristics for the weighted max cut‐clique problem
- A new branch-and-bound algorithm for the maximum edge-weighted clique problem
- The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
- Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
- Solving the maximum edge weight clique problem via unconstrained quadratic programming
- A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem
- A new family of facet defining inequalities for the maximum edge-weighted clique problem
- A cutting plane algorithm for a clustering problem
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
- scientific article; zbMATH DE number 3888925 (Why is no real title available?)
- scientific article; zbMATH DE number 3902051 (Why is no real title available?)
- scientific article; zbMATH DE number 3904604 (Why is no real title available?)
- scientific article; zbMATH DE number 3980481 (Why is no real title available?)
- scientific article; zbMATH DE number 3991298 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3895002 (Why is no real title available?)
- On the symmetric travelling salesman problem: Solution of a 120-city problem
- Optimisation en analyse des données relationnelles
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Solution of a Large-Scale Traveling-Salesman Problem
- An extended formulation approach to the edge-weighted maximal clique problem
- New facets and a branch-and-cut algorithm for the weighted clique problem.
- The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
- Correction to: ``Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts
- An iterated ``hyperplane exploration approach for the quadratic knapsack problem
- PUSH: A generalized operator for the maximum vertex weight clique problem
- A nonconvex quadratic optimization approach to the maximum edge weight clique problem
- Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems
- Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
- Solving the 0-1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm
- A new family of facet defining inequalities for the maximum edge-weighted clique problem
- A polyhedral approach for a constrained quadratic 0-1 problem
- A new branch-and-bound algorithm for the maximum edge-weighted clique problem
- A review on algorithms for maximum clique problems
- Maximum cut-clique problem: ILS heuristics and a data analysis application
- A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem
- scientific article; zbMATH DE number 26478 (Why is no real title available?)
- Disconnecting graphs by removing vertices: a polyhedral approach
- A Lagrangian relaxation approach to the edge-weighted clique problem
- A general purpose exact solution method for mixed integer concave minimization problems
- The quadratic knapsack problem -- a survey
This page was built for publication: A cutting-plane approach to the edge-weighted maximal clique problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1309944)