Abstract
The critical node detection problem describes a class of graph problems that involves identifying sets of nodes that influence a given graph metric. One variant of this problem is to find the nodes that – when removed from the graph – maximize the number of connected components in the remaining graph. This is an example of a practical problem with multiple real-world applications in epidemic control, immunization strategies, social networks, biology, etc. This paper proposes the use of a simple GA to identify the set of the critical nodes of the problem without designing special problem specific variation operators. Problem specific information is used only in the fitness function and the constraint handling technique. We show that this simple approach performs as well as state-of-art methods.
Citare
@Inproceedings{Suciu2021ASG,
author = {M. Suciu and Noémi Gaskó and Tamás Képes and R. Lung},
booktitle = {Hybrid Artificial Intelligence Systems},
title = {A Simple Genetic Algorithm for the Critical Node Detection Problem},
year = {2021}
}