Politopo baseado em distâncias para o problema clássico de coloração de vértices em grafos
Resumo
Neste trabalho, apresenta-se o modelo baseado em distâncias para o problema clássico de coloração de vértices em grafos (VCP). A formulação de programação linear inteira utiliza variáveis de decisão que representam a distância entre cores atribuídas para cada par de vértices distintos, no lugar de fornecer explicitamente tais cores. Mostra-se que há uma relação próxima entre esta formulação e o modelo baseado em orientação para o VCP, proposto também pelos autores deste trabalho. Em particular, prova-se que desigualdades indutoras de facetas para o modelo baseado em orientação podem ser traduzidas em desigualdades indutoras de facetas para o modelo baseado em distâncias e vice-versa.
Referências
Burke, E., Mareček, J., Parkes, A., and Rudová, H. (2010). A supernodal formulation of vertex colouring with applications in course timetabling. Annals of Operat. Research, 179:105–130.
Campêlo, M., Campos, V., and Corrêa, R. (2008). On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics, 156:1097–1111.
de Freitas, R., Dourado, M., and Szwarcfiter, J. (2010). Graph coloring and scheduling problems. 4th Latin American Workshop on Cliques in Graphs.
Dias, B. (2014). Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio. Master’s thesis, Instituto de Computação – Universidade Federal do Amazonas, in portuguese.
Dias, B., de Freitas, R., Maculan, N., and Marenco, J. (2017). Facet-inducing inequalities and a cut-and-branch for the bandwidth coloring polytope based on the orientation model. Electronic Notes in Discrete Mathematics, 62:141 – 146. LAGOS’17 – IX Latin and American Algorithms, Graphs and Optimization.
Dias, B. R. C., Rodrigues, R. F., and Szwarcfiter, J. (2013). On graph coloring problems with distance constraints. In Proc. of I Workshop on Distance Geometry and Appl. (DGA 2013).
Karp, R. (1972). Reducibility Among Combinatorial Problems. In Miller, R. E. and Thatcher, J. W., editors, Complexity of Computer Computations, pages 85–103. Plenum Press.
Koster, A. (1999). Frequency assignment: models and algorithms. PhD thesis, Univ. Maastricht.
Mehrotra, A. and Trick, M. (1996). A column generation approach for graph coloring. INFORMS Journal on Computing, 8:344–354.
Méndez-Díaz, I. and Zabala, P. (2006). A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 154(5):826–847.
Campêlo, M., Campos, V., and Corrêa, R. (2008). On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics, 156:1097–1111.
de Freitas, R., Dourado, M., and Szwarcfiter, J. (2010). Graph coloring and scheduling problems. 4th Latin American Workshop on Cliques in Graphs.
Dias, B. (2014). Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio. Master’s thesis, Instituto de Computação – Universidade Federal do Amazonas, in portuguese.
Dias, B., de Freitas, R., Maculan, N., and Marenco, J. (2017). Facet-inducing inequalities and a cut-and-branch for the bandwidth coloring polytope based on the orientation model. Electronic Notes in Discrete Mathematics, 62:141 – 146. LAGOS’17 – IX Latin and American Algorithms, Graphs and Optimization.
Dias, B. R. C., Rodrigues, R. F., and Szwarcfiter, J. (2013). On graph coloring problems with distance constraints. In Proc. of I Workshop on Distance Geometry and Appl. (DGA 2013).
Karp, R. (1972). Reducibility Among Combinatorial Problems. In Miller, R. E. and Thatcher, J. W., editors, Complexity of Computer Computations, pages 85–103. Plenum Press.
Koster, A. (1999). Frequency assignment: models and algorithms. PhD thesis, Univ. Maastricht.
Mehrotra, A. and Trick, M. (1996). A column generation approach for graph coloring. INFORMS Journal on Computing, 8:344–354.
Méndez-Díaz, I. and Zabala, P. (2006). A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 154(5):826–847.
Publicado
26/07/2018
Como Citar
DIAS, Bruno; DE FREITAS, Rosiane; MARENCO, Javier; MACULAN, Nelson.
Politopo baseado em distâncias para o problema clássico de coloração de vértices em grafos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 77-80.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3155.
