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)
Carlos Diego Rodrigues
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
http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1962Documentos Relacionados
- A study on the polytope and lower bounds of the representatives coloring formulation
- ConfiguraÃÃo de vÃrtices e efeitos de interface em supercondutores mesoscÃpicos
- DinÃmica de vÃrtices puntiformes em superfÃcies
- Fases de vÃrtices e antivÃrtices em filmes supercondutores com nanoestruturas magnÃticas
- ConfiguraÃÃo, anisotropia e defeitos em uma rede de vÃrtices na presenÃa de nanoarmadilhas