Busca avançada
Ano de início
Entree

Recoloração convexa de grafos

Processo: 18/04760-3
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de agosto de 2018
Vigência (Término): 30 de setembro de 2019
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Convênio/Acordo: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Pesquisador responsável:Zanoni Dias
Beneficiário:Ana Paula dos Santos Dantas
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Meta-heurística   Otimização combinatória   Programação matemática

Resumo

Dados um grafo G=(V,E), um conjunto de cores e uma coloração que define uma cor para os vértices de G, dizemos que a coloração é convexa se cada classe de cor induz um subgrafo conexo. Quando uma coloração não é convexa, é importante saber qual o menor número de recolorações são necessárias para alcançar essa propriedade. Uma recoloração convexa mínima é uma coloração obtida a partir de uma coloração não convexa com o menor número de vértices com cores trocadas. Esse problema surgiu a partir do estudo de árvores filogenéticas, em que a convexidade indica que não houveram convergências ou reversões durante a evolução de uma característica. Além da aplicação na biologia, o problema também pode ser aplicado a redes de computadores com poucas modificações. Neste projeto, estudaremos o problema com árvores e grafos gerais. Para isso, desenvolveremos algoritmos com a meta-heurística GRASP e modelos matemáticos para as versões estudadas do problema. Por fim, serão realizados experimentos com os algortimos e modelos desenvolvidos neste trabalho e os presentes na literatura, a fim de comparar desempenho e qualidade da solução. (AU)