Um algoritmo de planos-de-corte para o número cromático fracionário de um grafo

AUTOR(ES)

Campêlo, Manoel, Campos, Victor A., Corrêa, Ricardo C.

FONTE

Pesquisa Operacional

DATA DE PUBLICAÇÃO

2009-04

RESUMO

O número cromático fracionário χF(G) de um grafo G é um conhecido limite inferior para seu número cromático χ(G). Experimentos relatados na literatura mostram que usar χF(G), em lugar do tamanho da clique máxima, pode ser muito mais eficiente para orientar a busca em um algoritmo tipo branch-and-bound para determinação de χ(G). Uma dificuldade, porém, é tratar o modelo linear conhecido para χF(G), o qual apresenta um número exponencial de variáveis e demanda um caro processo de geração de colunas. Neste trabalho, examinamos uma formulação alternativa para obter um limite inferior para χF(G) que possui um número de variáveis linear no tamanho do grafo, porém um número exponencial de restrições. Utilizamos o método de planos-de-corte para lidar com esse inconveniente. Algumas heurísticas de separação são propostas, e experimentos computacionais mostram que valores muito próximos de χF(G), em muitos casos iguais, são encontrados em tempo inferior à implementação com geração de colunas.

ASSUNTO(S)

número cromático planos-de-corte otimização combinatória

Documentos Relacionados

• A Compreensão do conceito de número fracionário: uma sequência didática para o significado medida
• Resolução de um Problema Inverso Diferencial Fracionário no Processo de Fermentação Batelada Usando o Método da Colocação Ortogonal e o Algoritmo de Busca Fractal Estocástica
• Introdução do conceito de número fracionário e de suas representações: uma abordagem criativa para a sala de aula
• Propriedades espectrais de um grafo
• Uma heurística baseada em geração sequencial de padrões para o problema de corte de estoque unidimensional com um número reduzido de padrões