Finura em Grafos Cordais

  • Bernardo Amorim UFMG
  • Vinicius F. dos Santos UFMG

Resumo


A finura de um grafo é uma medida do "quão distante" um grafo está de um grafo de intervalo, sendo estes exatamente os grafos de finura 1. Neste artigo introduzimos um conceito análogo, a finura cordal, apresentando limites superiores e resultados parciais a respeito de sua complexidade computacional. Além disso, também determinamos a complexidade de problemas clássicos em grafos de finura cordal limitada. Em particular, mostramos que CONJUNTO INDEPENDENTE permanece NP-Difícil mesmo em grafos de finura cordal 3. Por outro lado, mostramos que é possível generalizar o resultado de polinomialidade de CLIQUE em grafos cordais para grafos de finura cordal 2.

Palavras-chave: Algoritmos, Complexidade Computacional, Teoria dos Grafos e Combinatória

Referências

Bonomo-Braberman, F. and Brito, G. A. (2021). Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs.

de Estrada, D. (2020). On the thinness and proper thinness of a graph. Discrete Applied Mathematics 261.

Mannino, C. (2007). The stable set problem and the thinness of a graph. Operations Research Letters.

Rose, D. J. and Tarjan, R. E. (1978). Algorithmic aspects of vertex elimination on directed graphs. SIAM Journal on Applied Mathematics, 34(1):176–197.
Publicado
31/07/2022
AMORIM, Bernardo; SANTOS, Vinicius F. dos. Finura em Grafos Cordais. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 73-76. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.223033.