A study on the polytope and lower bounds of the representatives coloring formulation / Um estudo do politopo e dos limites inferiores gerados pela formulaÃÃo de coloraÃÃo dos representantes
AUTOR(ES)
Victor Almeida Campos
DATA DE PUBLICAÇÃO
2005
RESUMO
O problema de coloraÃÃo de vÃrtices à considerado um dos modelos mais estudados em teoria dos grafos pela sua relevÃncia em campos prÃticos e teÃricos. Do ponto de vista teÃrico, o problema de coloraÃÃo à NP - DifÃcil. AlÃm disto, foi classificado entre os problemas mais difÃceis de NP, no sentido de que achar uma aproximaÃÃo para o nÃmero cromÃtico tambÃm à NP - DifÃcil. A importÃncia do problema de coloraÃÃo tem incentivado a investigar mÃtodos para encontrar limitantes inferiores prÃximos do nÃmero cromÃtico. Historicamente, os primeiros limitantes inferiores utilizados para resolvÃ-lo lidavam com cliques maximais. Mais recentemente, popularizou-se a utilizaÃÃo de relaxaÃÃes lineares de formulaÃÃes de programaÃÃo inteira. Uma formulaÃÃo que mostrou bons limitantes inferiores foi a formulaÃÃo por conjuntos independentes, cujo valor de relaxaÃÃo equivale ao nÃmero cromÃtico fracionÃrio. No presente trabalho, fazemos uma comparaÃÃo entre as formulaÃÃes de programaÃÃo inteira conhecidas para indicar a escolha pela formulaÃÃo dos representantes. Revisamos a formulaÃÃo para remover simetrias existentes e apresentamos um estudo parcial do politopo associado ao fecho convexo de suas soluÃÃes inteiras. Discutimos como à possÃvel utilizar a formulaÃÃo dos representantes para gerar limites inferiores para o nÃmero cromÃtico fracionÃrio. Realizamos a implementaÃÃo de um mÃtodo de planos de corte para aproximar o nÃmero cromÃtico fracionÃrio e mostramos que podemos gerar limitantes inferiores que normalmente nÃo diferem em mais de uma unidade.
ASSUNTO(S)
polyhedral theory teoria poliÃtrica teoria da computacao vertex coloring mÃtodo de planos-de-corte. integer programming coloraÃÃo de vÃrtice programaÃÃo inteira plan-of-cut method.
ACESSO AO ARTIGO
http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=2159Documentos Relacionados
- Limites inferiores para o problema de coloraÃÃo de vÃrtices via geraÃÃo de cortes e colunas
- Alcances e limites do exame citopatolÃgico com coloraÃÃo de Papanicolaou no diagnÃstico das cÃrvico-vaginites: um estudo citolÃgico e microbiolÃgico de 2169 casos de um total de 10.064 exames citopatolÃgicos
- FormulaÃÃo co-rotacional para pÃrticos planos.
- FormulaÃÃo MatemÃtica para CÃlculo de VariaÃÃo de ConcentraÃÃo em Escoamento EstacionÃrio
- Farinha dos resÃduos do camarÃo Litopenaeus vannamei : caracterizaÃÃo e utilizaÃÃo na formulaÃÃo de hambÃrguer