Politopo baseado em distâncias para o problema clássico de coloração de vértices em grafos

  • Bruno Dias
  • Rosiane de Freitas
  • Javier Marenco
  • Nelson Maculan

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.

Publicado
26/07/2018
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 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3157.