Número de envoltória em classes de grafos orientados⇤

  • J. Araújo
  • P. Arraes

Resumo


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 é NPcompleto 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.

Publicado
26/07/2018
ARAÚJO, J.; ARRAES, P.. Número de envoltória em classes de grafos orientados⇤. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3150.