Particularidades do Problema de Partição na Convexidade P3 em Grafos com Treewidth Limitada - de Castro, Lorrana F.; de Oliveira, Rodolfo A.; Protti, Fábio (Anais do Encontro de Teoria da Computação (ETC), 2020)
Neste trabalho, apresentamos um algoritmo que resolve o problema de partição na convexidade P3 quando restrito a grafos com treewidth limitada. Dados um grafo G = (V;E) e X ⊆ V , dizemos que X é um conjunto p3-convexo se todo vértice com pelo menos dois vizinhos em X também pertence a X. A coleção de todos os subconjuntos p3-convexos de V constitui a convexidade P3 em G. O problema da p-partição na convexidade P3 consiste em particionar V em p conjuntos p3-convexos não-vazios e mutualmente disjuntos, para um inteiro p ≥ 2. Apesar da NP-completude mesmo para grafos split, mostramos que o problema é resolvido em tempo linear para grafos com treewidth e o número p limitados.