SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem

DOI10.1016/j.artint.2019.103230zbMath1476.68218OpenAlexW2998631884WikidataQ126411384 ScholiaQ126411384MaRDI QIDQ2302299

Shaowei Cai, Minghao Yin, Yiyuan Wang, Jiejiang Chen

Publication date: 26 February 2020

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2019.103230

zbMATH Keywords

local searchmaximum weight clique problemmassive graphstrong configuration checkingwalk perturbation procedure

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

Solving the set packing problem via a maximum weighted independent set heuristic ⋮ Boosting ant colony optimization via solution prediction and machine learning ⋮ Many-objective evolutionary algorithm with adaptive reference vector ⋮ Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ An efficient local search algorithm for minimum positive influence dominating set problem ⋮ An improved configuration checking-based algorithm for the unicost set covering problem ⋮ A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs ⋮ SCCWalk

Uses Software

• QUALEX
• NuMVC
• DIMACS
• MaxCliqueDyn
• CCASat
• BBMCSP
• CCLS
• gpuls-mwcp

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Breakout local search for maximum clique problems
• A new exact maximum clique algorithm for large and massive sparse graphs
• An adaptive multistart tabu search approach to solve the maximum clique problem
• Local search for Boolean satisfiability with configuration checking and subscore
• Improving configuration checking for satisfiable random \(k\)-SAT instances
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Approximating the maximum vertex/edge weighted clique using local search
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• A fast algorithm for the maximum weight clique problem
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs
• PUSH: A generalized operator for the maximum vertex weight clique problem
• Multi-neighborhood tabu search for the maximum weight clique problem
• Probably bounded suboptimal heuristic search
• Many hard examples in exact phase transitions
• Phased local search for the maximum clique problem
• A new trust region technique for the maximum weight clique problem
• A hybrid heuristic for the maximum clique problem
• An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem
• Clique Relaxation Models in Social Network Analysis
• Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Tabu Search—Part I
• Approximating Maximum Clique by Removing Subgraphs
• NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover
• Reducibility among Combinatorial Problems
• Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess
• Theory and Applications of Satisfiability Testing
• MLQCC: an improved local search algorithm for the set k‐covering problem

This page was built for publication: SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem