Data: 22/10/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: From Decomposition Based Dynamic Programming to Automated Theorem Proving
Palestrante: Mateus de Oliveira Oliveira (Department of Informatics, University of Bergen)

Abstract: Many computational problems that are NP-complete, or even harder on general graphs admit efficient algorithms when restricted to classes of graphs of bounded width (such as treewidth, cliquewidth etc). These algorithms are typically dynamic programming operating on appropriate notions of graph decompositions. In this work, we introduce a general framework to transform state-of-the-art decomposition-based dynamic programming algorithms into algorithms that can be used to provide a parameterized attack for graph-theoretic conjectures.

This is joint work with Farhad Vadiee (University of Bergen)