voltarData: 27/11/2019
Título: Introdução sobre complexidade parametrizada e problemas.
Palestrantes: Prof. Ignasi Sau, LIRMM e Prof. Uerveton Souza, IC/UFF.
Data: 27 de Novembro de 2019, 13 h.
Local: Sala 407, Bloco H, Campus Gragoatá, UFF.
Resumo: 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.