Problemas de Particionamento de Grafos em Árvores Monocromáticas

• Diego Rangel Piranga Costa UFMG
• Vinicius Fernandes dos Santos UFMG
• Phablo F. S. Moura UFMG

DOI: https://doi.org/10.5753/etc.2022.223189

Resumo

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.

Palavras-chave: Algoritmos, Árvores Monocromáticas, Complexidade Parametrizada, Grafos

Referências

Bodlaender, H. L., Cygan, M., Kratsch, S., and Nederlof, J. (2013). Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86–111.

Jin, Z., Kano, M., Li, X., and Wei, B. (2006). Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycle, paths and trees. Journal of Combinatorial Optimization, 11(4):445–454.

Jin, Z. and Li, X. (2004). The complexity for partitioning graphs by monochromaic trees, cycles and paths. International Journal of Computer Mathematics, 81(11):1357–1362.

Jin, Z. and Li, X. (2008). Vertex partitions of r-edge-colored graphs. Applied Mathematics-A Journal of Chinese Universities, 23(1):120–126.