A complementary pivoting approach to the maximum weight clique problem

DOI10.1137/S1052623400381413MaRDI QIDQ2784445zbMATH OpenOpenAlexFDO

Authors Alessio Massaro, Marcello Pelillo, Immanuel M. Bomze

Publication date 23 April 2002

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s1052623400381413

zbMATH Keywords

combinatorial optimizationheuristicslinear complementaritymaximum weight cliquepivoting methodsquadratic programming

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Quadratic programming (90C20) Combinatorial optimization (90C27) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Extreme-point and pivoting methods (90C49) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A pivoting-based heuristic for the maximum clique problem.
• The combinatorics of pivoting for the maximum weight clique.
• A new algorithm for the maximum-weight clique problem
• On the Maximum Weight Clique Problem
• scientific article; zbMATH DE number 1786225

Cited in

(18)

• Simple ingredients leading to very efficient heuristics for the maximum clique problem
• Crashing a maximum-weight complementary basis
• A variable neighborhood search heuristic for the maximum ratio clique problem
• Maximum weight relaxed cliques and Russian doll search revisited
• A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs
• On independent cliques and linear complementarity problems
• On a continuous approach for the maximum weighted clique problem
• A new trust region technique for the maximum weight clique problem
• A hybrid heuristic for the maximum clique problem
• Quartic formulation of standard quadratic optimization problems
• A review on algorithms for maximum clique problems
• A pivoting-based heuristic for the maximum clique problem.
• Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata
• Fast cluster detection in networks by first order optimization
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• On the convergence of mirror descent beyond stochastic convex programming
• The combinatorics of pivoting for the maximum weight clique.
• Graph polynomials from principal pivoting

This page was built for publication: A complementary pivoting approach to the maximum weight clique problem

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