Introdução sobre complexidade parametrizada e problemas

Speakers: Ignasi Sau, LIRMM; Ueverton Souza, IC-UFF.

Date: 27 nov 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Nesta palestra faremos uma breve introdução sobre algoritmos e complexidade parametrizada, uma das áreas mais promissoras da teoria da computação. Em seguida serão apresentados alguns problemas de nosso interesse particular tais como deleção de vértices em grafos com bounded treewidth para obtenção de estruturas livres de certos subgrafos induzidos. Em especial abordaremos o desenvolvimento de algoritmos de tempo single-exponencial com relação a treewidth do grafo de entrada para resolução problemas como deleção de vértices para obtenção de grafos livres de conjuntos independentes induzidos de tamanho k.