Data e hora: sexta, 14 de abril de 2023, às 16h.
Local: sala 2077 (ICEx)
Palestrante: Guilherme Gomes (DCC, UFMG)
Título: Algoritmos e complexidade parametrizada para problemas em grafos
Resumo:
Na complexidade clássica, problemas são divididos entre aqueles que podem ser resolvidos em tempo polinomial no tamanho da entrada e os que acreditamos que não podem. Mesmo assim, precisamos resolver instâncias de problemas difíceis regularmente, e muitas vezes encontramos soluções ótimas muito mais rapidamente do que antecipávamos. Um dos arcabouços para explicar esse fenômeno é conhecido como complexidade parametrizada. Nele, algoritmos e problemas tem sua complexidade determinada por uma análise multivariada, onde levamos em conta o tamanho da entrada e parâmetros de interesse, como características desejadas da solução ou propriedades estruturais da entrada. Neste seminário, iremos explorar as definições básicas e direções de pesquisa da área, usando problemas em grafos como aplicações e exemplos.
