A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs

DOI10.1016/j.cor.2017.09.023zbMath1391.90527OpenAlexW2759387471MaRDI QIDQ1652526

Bruno Nogueira, Rian Gabriel S. Pinheiro

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2017.09.023

zbMATH Keywords

combinatorial optimizationmetaheuristicslocal searchcliqueGPUmaximum weight clique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Mathematical problems of computer architecture (68M07) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Boosting ant colony optimization via solution prediction and machine learning ⋮ Iterated local search with tabu search for the weighted vertex coloring problem ⋮ A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems ⋮ A FPGA-based accelerated architecture for the continuous GRASP ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ gpuls-mwcp

Uses Software

• CUDA
• ils-mwis

Cites Work

• Solving the maximum vertex weight clique problem via binary quadratic programming
• Breakout local search for maximum clique problems
• Fast local search for the maximum independent set problem
• A network-based data mining approach to portfolio selection via weighted clique relaxations
• Approximating the maximum vertex/edge weighted clique using local search
• Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems
• PUSH: A generalized operator for the maximum vertex weight clique problem
• Multi-neighborhood tabu search for the maximum weight clique problem
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Approximating Maximum Clique by Removing Subgraphs
• Reducibility among Combinatorial Problems

This page was built for publication: A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs