CAMPOS, Victor Almeida. Um estudo do politopo e dos limites inferiores gerados pela formulação de coloração dos representantes. 2005. 108 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2005. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T18:37:10Z
No. of bitstreams: 1
2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T12:41:39Z (GMT) No. of bitstreams: 1
2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) / Made available in DSpace on 2016-07-22T12:41:39Z (GMT). No. of bitstreams: 1
2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5)
Previous issue date: 2005 / The vertex coloring problem is one of the most studied problems in graph theory for its relevance in practical and theoretical fields. From a theoretical point of view, it is a NP-Hard problem. Moreover, it is classified among the most difficult problems of NP- Hard in the sense that finding an approximation to the chromatic number is also NP-Hard. The importance of the coloring problem motivates searching for methods to find lower bounds close to the chromatic number. Historically, the first lower bounds used were obtained from the size of maximal cliques. More recently, relaxed integer programming formulations gained more attention. A formulation which found good lower bounds was the coloring problem through stable sets whose relaxed lower bound equals the fractional chromatic number. In this work, we make a comparison between the known integer programming formulations to motivate our choice for the Representatives formulation. We revise this formulation to remove symmetry and present a partial study of the polytope associated with the convex hull of its integer solutions. We discuss how to se the Representatives formulation to get lower bounds for the fractional chromatic number and we show how to get such lower bounds that differ at most by one unit to its exact value. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufc.br:riufc/18654 |
| Date | January 2005 |
| Creators | Campos, Victor Almeida |
| Contributors | Corrêa, Ricardo Cordeiro |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds