Return to search

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

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. / In this work the vertex coloring problem is approached via integer programming. A tighter version of the independent set formulation is used, where the vertex-related constraints are substituted by subgraph-related constraints. Each constraint establishes a lower bound on the number of independent sets intersecting a subgraph H. It is shown a sufficient condition for this inequality to define a facet of the associated polytope. Basically, H is required to be color critical, not included in another color critical subgraph, and to have
a connected complement. Also, the column generation algorithm
proposed by Mehotra and Trick (INFORMS Journal in Computing, 1996) is adapted to allow the addition of cutting planes and to provide lower bounds along the process, which may abbreviate its end. Some computational experiments are reported.

Identiferoai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:1738
Date22 November 2008
CreatorsCarlos Diego Rodrigues
ContributorsManoel Bezerra Campelo Neto, Ricardo Cordeiro CorrÃa, Philippe Yves Paul Michelon, Susana Scheimberg de Makler
PublisherUniversidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0019 seconds