Finura em Grafos Cordais
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.
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
Como Citar
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.
