Approximating the maximum vertex/edge weighted clique using local search

DOI10.1007/s10732-007-9026-2zbMath1173.90569OpenAlexW2094314299MaRDI QIDQ1009183

Wayne Pullan

Publication date: 31 March 2009

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-007-9026-2

zbMATH Keywords

local searchmaximum weighted clique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (22)

A review on algorithms for maximum clique problems ⋮ Solving the maximum vertex weight clique problem via binary quadratic programming ⋮ Clustered maximum weight clique problem: algorithms and empirical analysis ⋮ A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs ⋮ Breakout local search for maximum clique problems ⋮ Performance evaluation of a parallel ant colony optimization for the real-time train routing selection problem in large instances ⋮ An efficient local search algorithm for solving maximum edge weight clique problem in large graphs ⋮ MLQCC: an improved local search algorithm for the set k‐covering problem ⋮ Complexity and heuristics for the weighted max cut‐clique problem ⋮ On the Approximability of the Minimum Weight $t$-partite Clique Problem ⋮ Parallelization of a branch-and-bound algorithm for the maximum weight clique problem ⋮ A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs ⋮ A hybrid iterated local search heuristic for the maximum weight independent set problem ⋮ PUSH: A generalized operator for the maximum vertex weight clique problem ⋮ A nonconvex quadratic optimization approach to the maximum edge weight clique problem ⋮ A new branch-and-bound algorithm for the maximum weighted clique problem ⋮ Multi-neighborhood tabu search for the maximum weight clique problem ⋮ Solving the maximum edge-weight clique problem in sparse graphs with compact formulations ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ Common Object Discovery as Local Search for Maximum Weight Cliques in a Global Object Similarity Graph ⋮ A maximum edge-weight clique extraction algorithm based on branch-and-bound

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating maximum independent sets by excluding subgraphs
• A fast algorithm for the maximum weight clique problem
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Annealed replication: A new heuristic for the maximum clique problem
• An application of tabu search heuristic for the maximum edge-weighted subgraph problem
• Phased local search for the maximum clique problem
• Finding a Maximum Clique in an Arbitrary Graph

This page was built for publication: Approximating the maximum vertex/edge weighted clique using local search