Algoritmos e complexidade de problemas em grafos e em jogos combinatórios

Nesta linha de pesquisa, estamos interessados em determinar o quão eficientemente problemas podem ser resolvidos. Os problemas abordados incluem problemas em grafos e também jogos combinatórios.

Tipicamente, são desenvolvidos algoritmos de tempo polinomial quando os problemas são passíveis de resolução eficiente, ou são elaboradas demonstrações de NP-dificuldade, quando os problemas se enquadram nesta classe de complexidade. Para problemas difíceis, diversas abordagens são utilizadas, seja desenvolvendo algoritmos exatos exponenciais, algoritmos parametrizados ou mesmo restringindo a entrada a certos conjuntos bem comportados, como classes de grafos, de forma que a estrutura adicional da entrada permita o desenvolvimento de algoritmos eficientes.