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

DOI10.1016/J.ARTINT.2019.103230MaRDI QIDQ2302299zbMATH OpenOpenAlexWikidataFDO

Authors Yiyuan Wang, Shaowei Cai, Jiejiang Chen, Minghao Yin

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 searchmassive graphmaximum weight clique problemstrong configuration checkingwalk perturbation procedure

Mathematics Subject Classification ID

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

Recommendations

• An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
• A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs
• Multi-neighborhood tabu search for the maximum weight clique problem
• Breakout local search for maximum clique problems
• A new algorithm for the maximum-weight clique problem

Cites work

• A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs
• A fast algorithm for the maximum weight clique problem
• A hybrid heuristic for the maximum clique problem
• A new exact maximum clique algorithm for large and massive sparse graphs
• A new trust region technique for the maximum weight clique problem
• An adaptive multistart tabu search approach to solve the maximum clique problem
• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
• An improved branch and bound algorithm for the maximum clique problem
• Approximating Maximum Clique by Removing Subgraphs
• Approximating the maximum vertex/edge weighted clique using local search
• Breakout local search for maximum clique problems
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Clique relaxation models in social network analysis
• Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess
• Graph domination, coloring and cliques in telecommunications
• scientific article; zbMATH DE number 5547826 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• scientific article; zbMATH DE number 1786225 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• Improving configuration checking for satisfiable random \(k\)-SAT instances
• Local search for Boolean satisfiability with configuration checking and subscore
• Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Many hard examples in exact phase transitions
• MLQCC: an improved local search algorithm for the set k‐covering problem
• Multi-neighborhood tabu search for the maximum weight clique problem
• NuMVC: an efficient local search algorithm for minimum vertex cover
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• Phased local search for the maximum clique problem
• Probably bounded suboptimal heuristic search
• PUSH: A generalized operator for the maximum vertex weight clique problem
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Reducibility among combinatorial problems
• Tabu Search—Part I
• Theory and Applications of Satisfiability Testing

Cited in

(13)

• A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs
• Boosting ant colony optimization via solution prediction and machine learning
• An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
• An improved configuration checking-based algorithm for the unicost set covering problem
• Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism
• Breakout local search for maximum clique problems
• SCCWalk
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• Many-objective evolutionary algorithm with adaptive reference vector
• An efficient local search algorithm for minimum positive influence dominating set problem
• Improving local search algorithm for pseudo Boolean optimization
• Towards more efficient local search for weighted graph coloring problem in massive graphs
• Solving the set packing problem via a maximum weighted independent set heuristic

Describes a project that uses

Uses Software

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

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

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