Tratabilidade por Parâmetro Fixo para Largura em Árvore de Grafos Direcionados - Maia, A. Karolinna; Lopes, Raul; Campos, Victor (Anais do Encontro de Teoria da Computação (ETC); 2018: Anais do III Encontro de Teoria da Computação, 2018)
A largura em árvore de um grafo não-direcionado G é uma medida de quão similar G é de uma árvore. Uma definição análoga também é conhecida para grafos direcionados. Para k constante, nós melhoramos um resultado conhecido mostrando um algoritmo FPT, com parâmetro k, que decide se a largura em árvore de um grafo direcionado D é no máximo 3k − 2 ou se D admite um refúgio de ordem k.