Tratabilidade por Parâmetro Fixo para Largura em Árvore de Grafos Direcionados⇤

  • A. Karolinna Maia
  • Raul Lopes
  • Victor Campos
DOI: https://doi.org/10.5753/etc.2018.3163

Resumo


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.

Publicado
26/07/2018
Como Citar

Selecione um Formato
MAIA, A. Karolinna; LOPES, Raul; CAMPOS, Victor. Tratabilidade por Parâmetro Fixo para Largura em Árvore de Grafos Direcionados⇤. 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.3163.