The search functionality is under construction.

IEICE TRANSACTIONS on Information

Cluster Expansion Method for Critical Node Problem Based on Contraction Mechanism in Sparse Graphs

Zheng WANG, Yi DI

  • Full Text Views

    0

  • Cite this

Summary :

The objective of critical nodes problem is to minimize pair-wise connectivity as a result of removing a specific number of nodes in the residual graph. From a mathematical modeling perspective, it comes the truth that the more the number of fragmented components and the evenly distributed of disconnected sub-graphs, the better the quality of the solution. Basing on this conclusion, we proposed a new Cluster Expansion Method for Critical Node Problem (CEMCNP), which on the one hand exploits a contraction mechanism to greedy simplify the complexity of sparse graph model, and on the other hand adopts an incremental cluster expansion approach in order to maintain the size of formed component within reasonable limitation. The proposed algorithm also relies heavily on the idea of multi-start iterative local search algorithm, whereas brings in a diversified late acceptance local search strategy to keep the balance between interleaving diversification and intensification in the process of neighborhood search. Extensive evaluations show that CEMCNP running on 35 of total 42 benchmark instances are superior to the outcome of KBV, while holding 3 previous best results out of the challenging instances. In addition, CEMCNP also demonstrates equivalent performance in comparison with the existing MANCNP and VPMS algorithms over 22 of total 42 graph models with fewer number of node exchange operations.

Publication
IEICE TRANSACTIONS on Information Vol.E105-D No.6 pp.1135-1149
Publication Date
2022/06/01
Publicized
2022/02/24
Online ISSN
1745-1361
DOI
10.1587/transinf.2021EDP7150
Type of Manuscript
PAPER
Category
Fundamentals of Information Systems

Authors

Zheng WANG
  Hubei University of Economics
Yi DI
  Hubei University of Economics

Keyword