Número de envoltória em classes de grafos orientados - Araújo, J.; Arraes, P. (Anais do Encontro de Teoria da Computação (ETC); 2018: Anais do III Encontro de Teoria da Computação, 2018)
Neste trabalho estudamos o número de envoltória para algumas classes de grafos orientados. Primeiramente apresentamos um limitante superior para o número de envoltória restrito a torneios, além de um torneio para o qual atingimos esse limite. Em seguida provamos que esse problema é NP-completo para grafos bipartidos orientados. Para tanto utilizamos o resultado de [Araujo et al. 2013], o qual afirma que tal problema é NP-completo para grafos bipartidos não-orientados. Depois mostramos uma caraterização para o menor conjunto de envoltória de umaárvore orientada. Além disso, generalizamos esse resultado ao mostrar um algoritmo de tempo polinomial para calcular o número de envoltória de qualquer grafo cacto orientado.