Complexidade Parametrizada (2017)
Horário: Segunda e Quarta de 09:00 às 11:00
Sala 315
Programa do Curso
- A classe P.
- A classe NP.
- Reduções de tempo polinomial.
- NP-completude e NP-dificuldade.
- Técnicas para contornar a intratabilidade de problemas difíceis.
- A classe XP.
- A classe FPT.
- Árvores de busca com altura limitada.
- O método de redução a um núcleo (kernelização).
- Kernelização x Pré-processamento.
- Intratabilidade Parametrizada.
- A classe W[1].
- A classe W[2].
- W-hierarquia.
- W[P] e W[Sat].
- Núcleos (kernels) de tamanho polinomiais.
- Inviabilidade de núcleos polinomiais.
Bibliografia:
- Michael R. Garey, David S. Johnson. Computer and intractability. A Guide to the NP-Completeness. Ney York, NY: WH Freeman and Company, 1979.
- Rodney G. Downey, Michael R. Fellows. Fundamentals of Parameterized Complexity, Springer, 2013.
- Rodney G. Downey, Michael R. Fellows. Parameterized complexity, Monographs in Computer Science, Springer, 1999.
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. Parameterized Algorithms, Springer, 2015.
- Jörg Flum; Martin Grohe. Parameterized complexity theory, Springer, 2006.
- Rolf Niedermeier. Invitation to fixed-parameter algorithms, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, 2006.
Material Complementar:
- Uma introdução à complexidade parametrizada
- Slides 1
- Slides 2
- Slides 3
- Intratabilidade Parametrizada (Slides Wopoca)