Metaheurísticas para o problema de dominação romana perfeita em grafos

Abstract

Given a graph G, a function f :V(G)→{0,1,2} is called a Perfect Roman Dominating Function (PRDF) of G if, for every vertex v in G with f(v) = 0, there exists exactly one adjacent vertex u such that f(u) = 2. The weight of the function f is defined as ω(f) = ∑v∈V(G) f(v). The perfect Roman domination number, denoted by γp R(G), corresponds to the minimum value of ω(f) among all perfect Roman dominating functions f of G. A PRDF with minimum weight is called optimal. The perfect Roman domination problem has been the subject of study in recent years and has been shown to be NP-complete for various graph classes. In this undergraduate thesis, were developed two metaheuristics based on genetic algorithms: the first follows a classical approach, while the second is based on the biased random-key genetic algorithm model. Additionally, a integer programming model was implemented in order to provide an exact approach for comparison with the metaheuristic results. Solutions were obtained for different classes of graphs and compared through execution time and fitness value.