SCIENCE@home

An Efficient Local Search for the Maximum Edge Weighted Clique Problem

Ruizhi Li,Xiaoli Wu,Huan Liu,Jun Wu,Minghao Yin

Published 2018 in IEEE Access

ABSTRACT

The maximum edge weighted clique problem (MEWCP), an extension of the classical maximum clique problem, is an important NP-hard combinatorial optimization problem. The problem has been widely used in various areas. The objective of this paper is to design an efficient local search algorithm to solve the MEWCP. First, the proposed scoring strategy is used to evaluate the benefit of adding and swapping operators. Second, the vertex weighting strategy is used to increase the diversity of solutions and the configuration checking strategy is used to avoid the cycling problem. By combining these three strategies, we propose multiple rules to select the added vertex or the swapped vertex pair. Based on the multiple rules, an efficient local search algorithm, namely, local search based on multiple rules (LSMR), is proposed. LSMR is compared with several representative algorithms on massive graph instances. The experimental results indicate that LSMR is superior to competitors in terms of solution quality and computational efficiency in most instances.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-41 of 41 references · Page 1 of 1

CITED BY

Showing 1-14 of 14 citing papers · Page 1 of 1