Calculando o número de envoltória nas convexidades P3 e P3* - Araújo, J.; Campêlo, M.; de Sousa, G. H. (Anais do Encontro de Teoria da Computação (ETC); 2018: Anais do III Encontro de Teoria da Computação, 2018)
Um subconjunto de vértices S em um grafo G = (V, E) é convexo na convexidade P 3 (resp. P 3 *) se todo vértice v ∈ V (G) \ S não possuir dois vizinhos (resp. que não sejam adjacentes entre si) em S. A envoltória convexa de S é o menor conjunto convexo que o contém. Um conjunto de envoltória é um conjunto cuja envoltória convexa é V (G). O número de envoltória é a cardinalidade de um conjunto de envoltória mínimo. Neste trabalho, propomos e estudamos duas formulações de programação linear-inteira para determinar o número de envoltória de um grafo nas convexidades P3 e P 3 *, que acreditamos serem as primeiras na literatura. Realizamos experimentos computacionais para avaliar seus desempenhos.