A cutting-plane approach to the edge-weighted maximal clique problem
type: Item
instance of: scholarly article
title: A cutting-plane approach to the edge-weighted maximal clique problem
zbMATH Open document ID: 0787.90059
DOI: 10.1016/0377-2217(93)90097-7
published in: European Journal of Operational Research
publication date: 1993-12-20T00:00:00Z
full work available at URL: a-cuttingplane-approach-to-the-edgeweighted-maximal-clique-problem(d71fe2ad-5fff-467b-b3f6-5315e3f78b33).html
review text: 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.
reviewed by: Peter Brucker
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 90B80
zbMATH DE Number: 474806
zbMATH Keywords: maximal clique problem
zbMATH Keywords: complete undirected graph
zbMATH Keywords: cutting planes
Wikidata QID: Q60395645
author: Gert Dijkhuizen
author: U. Faigle
describes a project that uses: LOLIB
MaRDI profile type: Publication
OpenAlex ID: W2093716880
cites work: Solution of a Large-Scale Traveling-Salesman Problem
cites work: Q3682497
cites work: Q3753826
cites work: Q4198056
cites work: On the symmetric travelling salesman problem: Solution of a 120-city problem
cites work: A Cutting Plane Algorithm for the Linear Ordering Problem
cites work: A cutting plane algorithm for a clustering problem
cites work: Q3221421
cites work: Q5187226
cites work: Q3945368
cites work: Optimization of a 532-city symmetric traveling salesman problem by branch and cut
cites work: Q3680289
cites work: Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
cites work: Q3745273
Recommended article: An extended formulation approach to the edge-weighted maximal clique problem
Recommended article: Q3983239
Recommended article: Complexity and heuristics for the weighted max cut‐clique problem
Recommended article: A new branch-and-bound algorithm for the maximum edge-weighted clique problem
Recommended article: The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
Recommended article: Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
Recommended article: Solving the maximum edge weight clique problem via unconstrained quadratic programming
Recommended article: A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem
Recommended article: A new family of facet defining inequalities for the maximum edge-weighted clique problem
description: scientific article; zbMATH DE number 474806