Uma abordagem heurística ao problema de infecção em grafos submetido à regras P3 e P4

Abstract

The graph infection problem can be seen as a set of S infected vertices spreading a virus on a graph G = (V;E). In graph infection problems, uninfected vertices will be infected at a time i if they comply with the infection rules previously defined according to the time problem i - 1 (DRAIEF; GANESH, 2010). We studied the problem of determining the smallest set of infected graph vertices that can infect the entire graph. A mathematical model is proposed for each infection rule studied, in this case, P3 and P4, and then we started to implement the algorithms using the Python programming language PuLP library for handling the ILOG IBM CPLEX solver. At the end of the implementations, it can be seen that the model obtained promising results. Also presented is a constructive heuristic for the problem that was also tested with promising results, often obtaining results that exceed the values obtained in the optimal algorithms implemented, in relation to instances with high quantities of vertices..