Problemas de Particionamento de Grafos em Árvores Monocromáticas - Costa, Diego Rangel Piranga; Santos, Vinicius Fernandes dos; Moura, Phablo F. S. (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.223189, 2022)
Problemas de partição de grafos é uma importante classe de problemas de grafos que são capazes de modelar tarefas do mundo real, como, alocação concorrente de processadores e integração de sistemas de larga escala (VLSI). Mesmo tais problemas sendo NP-difíceis, existe muito esforço em desenvolver métodos para tratar tais problemas. Neste trabalho apresentamos resultados do ponto de vista de complexidade computacional para o Problema de Partição de Grafos em Árvores Monocromáticas conhecido como PGMT, onde demonstramos a NP-dificuldade mesmo para versões restritas do problema. Além disso, apresentamos um limitante inferior para o tempo de execução de algoritmos baseados na Hipótese do Tempo Exponencial (ETH) e também apresentamos dois algoritmos, um baseado em programação dinâmica quando consideramos que o grafo da entrada é uma árvore e um outro algoritmo parametrizado pela largura arbórea e pelo número de cores.