Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

Dado um grafo G = (V,E), um subconjunto S de V(G) é convexo (na convexidade geodésica) se, para todos u,v em S, os vértices em qualquer u,v-caminho mínimo também pertencem a S. A envoltória convexa de S, denotada por [S], é o menor conjunto convexo que contém S. O subconjunto S é um conjunto de envoltória se [S] = V(G). O número de envoltória de G, denotado por hn(G), é o menor k tal que G possui um conjunto de envoltória de cardinalidade k.É conhecido na literatura que determinar o número de envoltória de um grafo dado é um problema NP-Difícil, mesmo para cubos parciais, que formam uma subclasse de bipartidos.
Além disso, existem algoritmos polinomiais e limitantes para algumas classes de grafos, além de, mais recentemente, alguns resultados em Complexidade Parametrizada. Neste trabalho, dois modelos matemáticos e uma heurística para se calcular este parâmetro são estudados, implementados e comparados.