Impacto de Técnicas de Pré-Processamento em Algoritmo de Branch-and-Price para o Problema de Coloração de Grafos
Resumo
Este trabalho investiga o problema de coloração de vértices, o qual possui aplicações em escalonamento e alocação de recursos. Descrevemos um pré-processamento que utiliza técnicas de separação e redução (k-core ) para diminuir o espaço de busca sem comprometer limites inferiores válidos. Resultados experimentais com instâncias do DIMACS demonstram que o pré-processamento aumenta a quantidade de instâncias resolvidas, apesar de, em alguns casos, a ordem com que as partes do grafo são resolvidas por comprometer a capacidade de resolvê-lo. Concluimos com sugestões para trabalhos futuros, como a incorporação de separadores por clique.
Referências
Caprara, A., Kroon, L., Monaci, M., Peeters, M., and Toth, P. (2007). Chapter 3 Passenger Railway Optimization, pages 129–187. Elsevier.
Chow, F. C. and Hennessy, J. L. (1990). The priority-based coloring approach to register allocation. ACM Transactions on Programming Languages and Systems, 12(4):501–536.
de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19(2):151–162.
DIMACS (2002). Graph coloring instances. [link]. [Accessed 31-03-2025].
Gamache, M., Hertz, A., and Ouellet, J. O. (2007). A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding. Computers Operations Research, 34(8):2384–2395.
Garey, M. and Johnson, D. (1976). The complexity of near-optimal graph coloring. Journal of the ACM, 23(1):43–49.
Gurobi Optimization, LLC (2024). Gurobi Optimizer Reference Manual.
Malliaros, F. D., Giatsidis, C., Papadopoulos, A. N., and Vazirgiannis, M. (2019). The core decomposition of networks: theory, algorithms and applications. The VLDB Journal, 29(1):61–92.
Mehrotra, A. and Trick, M. A. (1996). A column generation approach for graph coloring. INFORMS Journal on Computing, 8(4):344–354.
Seidman, S. B. (1983). Network structure and minimum degree. 5(3):269–287.
Smith, D., Hurley, S., and Thiel, S. (1998). Improving heuristics for the frequency assignment problem. European Journal of Operational Research, 107(1):76–86.
Tarjan, R. (1985). Decomposition by clique separators. Discrete Mathematics, 55(2):221–232.
Xiao, M., Huang, S., Zhou, Y., and Ding, B. (2021). Efficient reductions and a fast algorithm of maximum weighted independent set. In Proceedings of the Web Conference 2021, WWW ’21. ACM.
Chow, F. C. and Hennessy, J. L. (1990). The priority-based coloring approach to register allocation. ACM Transactions on Programming Languages and Systems, 12(4):501–536.
de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19(2):151–162.
DIMACS (2002). Graph coloring instances. [link]. [Accessed 31-03-2025].
Gamache, M., Hertz, A., and Ouellet, J. O. (2007). A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding. Computers Operations Research, 34(8):2384–2395.
Garey, M. and Johnson, D. (1976). The complexity of near-optimal graph coloring. Journal of the ACM, 23(1):43–49.
Gurobi Optimization, LLC (2024). Gurobi Optimizer Reference Manual.
Malliaros, F. D., Giatsidis, C., Papadopoulos, A. N., and Vazirgiannis, M. (2019). The core decomposition of networks: theory, algorithms and applications. The VLDB Journal, 29(1):61–92.
Mehrotra, A. and Trick, M. A. (1996). A column generation approach for graph coloring. INFORMS Journal on Computing, 8(4):344–354.
Seidman, S. B. (1983). Network structure and minimum degree. 5(3):269–287.
Smith, D., Hurley, S., and Thiel, S. (1998). Improving heuristics for the frequency assignment problem. European Journal of Operational Research, 107(1):76–86.
Tarjan, R. (1985). Decomposition by clique separators. Discrete Mathematics, 55(2):221–232.
Xiao, M., Huang, S., Zhou, Y., and Ding, B. (2021). Efficient reductions and a fast algorithm of maximum weighted independent set. In Proceedings of the Web Conference 2021, WWW ’21. ACM.
Publicado
20/07/2025
Como Citar
ROMERO, Ieremies V. F.; SCHOUERY, Rafael C. S..
Impacto de Técnicas de Pré-Processamento em Algoritmo de Branch-and-Price para o Problema de Coloração de Grafos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 124-128.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.9224.
