Limites inferiores para o problema de coloraÃÃo de vÃrtices via geraÃÃo de cortes e colunas / Inferior limits for the problem of vertex coloring saw generation of cuts and columns

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

22/11/2008

RESUMO

Neste trabalho abordamos o problema de coloraÃÃo de vÃrtices via programaÃÃo inteira. Uma versÃo expandida da formulaÃÃo por conjuntos independentes à utilizada para abrigar outras sub-estruturas do grafos alÃm dos vÃrtices. Cada uma dessas sub-estruturas define uma restriÃÃo que determina quantos conjuntos independentes sÃo necessarios para cobrir aquele subgrafo. Experimentos com um mÃtodo de geraÃÃo de cortes e colunas para o problema sÃo feitos para determinar um limite inferior para um conjunto de instÃncias classicas para esse problema a biblioteca DIMACS.

ASSUNTO(S)

ciencia da computacao coloraÃÃo de vÃrtices vertex coloring

ACESSO AO ARTIGO

Documentos Relacionados