Uma abordagem de programação matemática para o número de envoltória de um grafo

Abstract

The hull number of an undirected graph G = (V;E), where V is the set of vertices and E is the set of edges, consists of the smallest number of vertices that, initially contaminated, can iteratively contaminate the whole graph. The types of contamination (convexity) studied in this work were geodetic, P3, and P3∗. Determining the hull number is an NP-hard problem, even for bipartite graphs. In this work, mathematical models and heuristics for the problem were studied and implemented. To solve the models, the CPLEX was used, coupled with the C ++ programming. The same language was used to code the heuristic. The graphs used as test instances were bipartite and arbitrary graphs, created from two parameters: the number of vertices and a probability factor to define the existence of edges. The results presented by each model and the heuristic, related to the execution time and solution quality, were stored and compared.