Calculando o número de envoltória nas convexidades P3 e P3*
Resumo
Um subconjunto de vértices S em um grafo G = (V, E) é convexo na convexidade P3 (resp. P3*) 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 P3*, que acreditamos serem as primeiras na literatura. Realizamos experimentos computacionais para avaliar seus desempenhos.
Referências
Convexity properties of graphs on sagemath. [link]. Accessed: 2018-03-27.
Araújo, R., Sampaio, R., and Szwarcfiter, J. (2013). The convexity of induced paths of order three. Electronic Notes in Discrete Mathematics, 44:109 – 114.
Draque Penso, L., Protti, F., Rautenbach, D., and Souza, U. S. (2014). On p3-convexity of graphs with bounded degree. In Gu, Q., Hell, P., and Yang, B., editors, Algorithmic Aspects in Information and Management, pages 263–274, Cham. Springer International Publishing.
Duchet, P. (1988). Convex sets in graphs, ii. minimal path convexity. Journal of Combinatorial Theory, Series B, 44(3):307 – 316.
Farber, M. and Jamison, R. E. (1986). Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Methods, 7:433–444.
Araújo, R., Sampaio, R., and Szwarcfiter, J. (2013). The convexity of induced paths of order three. Electronic Notes in Discrete Mathematics, 44:109 – 114.
Draque Penso, L., Protti, F., Rautenbach, D., and Souza, U. S. (2014). On p3-convexity of graphs with bounded degree. In Gu, Q., Hell, P., and Yang, B., editors, Algorithmic Aspects in Information and Management, pages 263–274, Cham. Springer International Publishing.
Duchet, P. (1988). Convex sets in graphs, ii. minimal path convexity. Journal of Combinatorial Theory, Series B, 44(3):307 – 316.
Farber, M. and Jamison, R. E. (1986). Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Methods, 7:433–444.
Publicado
26/07/2018
Como Citar
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
.
p. 153-156.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3176.
