An Efficient Local Search for the Maximum Edge Weighted Clique Problem | Zendy

Ruizhi Li | Zendy; Xiaoli Wu | Zendy; Huan Liu | Zendy; Jun Wu | Zendy; Minghao Yin | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An Efficient Local Search for the Maximum Edge Weighted Clique Problem

Author(s) -

Ruizhi Li,

Xiaoli Wu,

Huan Liu,

Jun Wu,

Minghao Yin

Publication year - 2018

Publication title -

ieee access

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.587

H-Index - 127

ISSN - 2169-3536

DOI - 10.1109/access.2018.2799953

Subject(s) - aerospace , bioengineering , communication, networking and broadcast technologies , components, circuits, devices and systems , computing and processing , engineered materials, dielectrics and plasmas , engineering profession , fields, waves and electromagnetics , general topics for engineers , geoscience , nuclear engineering , photonics and electrooptics , power, energy and industry applications , robotics and control systems , signal processing and analysis , transportation

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research