Combinatorial Optimization on Graphs
[Introduction][Vertex Cover Problems] [Clique Problems ] [Coloring Problems] [Graph Benchmarks]
Heuristic algorithms for Maximum (Weight) Clique Problems
A clique of
a graph is a subset of the vertices that are all pairwise adjacent.
Clique is an important graph-theoretic concept, and
is often used to represent dense clusters. The maximum
clique problem (MaxClq) is a long-standing problem in graph
theory, for which the task is to find a clique with the maximum
number of vertices in the given graph. An important
generalization of MaxClq is the maximum weight clique problem
(MaxWClq), in which each vertex is associated with a positive
integer, and the goal is to find a clique with the largest
weight. MWCPhas valuable applications in many fields
Solvers for MaxWClq
FastWClq works in a construct-and-reduce way, which interleaves between clique
construction and graph reduction. FastWClq works particularly well for large sparse graphs.
---Reference: Shaowei Cai, Jinkun Lin: Fast Solving Maximum Weight Clique Problem in Massive Graphs. In Proc. of IJCAI 2016: 568-574
LSCC is a local search solver for MaxWClq and is good at dense graphs. LSCC+BMS is an improved version of LSCC for large sparse graphs. For more information, please visit pages of
Yiyuan Wang---Reference: Yiyuan Wang, Shaowei Cai, Minghao Yin: Two Efficient Local Search Algorithms for Maximum Weight Clique Problem. AAAI 2016: 805-811