Calculando o número de envoltória nas convexidades P3 e P3⇤ †

  • J. Araújo
  • M. Campêlo
  • G. H. de Sousa

Resumo


Um subconjunto de vértices S em um grafo G = (V, E) é convexo na convexidade P3 (resp. P 3⇤ ) se todo vértice v 2 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.

Publicado
26/07/2018
ARAÚJO, J.; CAMPÊLO, M.; DE SOUSA, G. H.. Calculando o número de envoltória nas convexidades P3 e P3⇤ †. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3176.