Cobertura Exata por Caminhos Arco-Íris com Conflitos em Grafos Tricoloridos
Resumo
Este trabalho estuda o problema COBERTURA EXATA POR CAMINHOS ARCO-ÍRIS COM CONFLITOS EM GRAFOS TRICOLORIDOS (3ERC), no qual, dado um grafo com arestas coloridas com três cores e uma lista de pares de vértices em conflito, deseja-se cobrir todas as arestas com o menor número de caminhos arco-íris válidos (disjuntos nas arestas e que não contêm pares em conflito). Demonstra-se que o problema é NP-difícil por redução a partir de EMPARELHAMENTO TRIDIMENSIONAL. Também é apresentado um algoritmo polinomial baseado em emparelhamento máximo que garante uma 2-aproximação.
Referências
Chartrand, G., Johns, G. L., McKeon, K. A., and Zhang, P. (2008). Rainbow connection in graphs. Mathematica Bohemica, 133(1):85–98.
Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467.
Karp, R. (1972). Reducibility among combinatorial problems. volume 40, pages 85–103.
Siewiorek, D. P. and Swarz, R. S. (1998). Reliable Computer Systems: Design and Evaluation. AK Peters.
Williamson, D. P. and Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press.
Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467.
Karp, R. (1972). Reducibility among combinatorial problems. volume 40, pages 85–103.
Siewiorek, D. P. and Swarz, R. S. (1998). Reliable Computer Systems: Design and Evaluation. AK Peters.
Williamson, D. P. and Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press.
Publicado
19/07/2026
Como Citar
SOUZA, Gustavo Henrique Sencio de; RAVELO, Santiago Valdés.
Cobertura Exata por Caminhos Arco-Íris com Conflitos em Grafos Tricoloridos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 70-74.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.23557.
