Busca avançada
Ano de início
Entree

Algoritmos para coloração de grafos

Processo: 20/09330-7
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de novembro de 2020
Vigência (Término): 31 de outubro de 2021
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Carla Negri Lintzmayer
Beneficiário:Wesley Lima de Araujo
Instituição-sede: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brasil
Assunto(s):Algoritmos   Grafos   Otimização combinatória   Análise de algoritmos

Resumo

Um problema é de otimização combinatória se ele visa encontrar soluções de um certo domínio que minimizam ou maximizam determinada função. Essas características são inerentes a diversos problemas importantes do mundo atual, provenientes de diversas áreas. Infelizmente, muitos problemas de otimização combinatória são NP-difíceis, fazendo com que não tenhamos esperança em encontrar algoritmos eficientes que os resolvam. A estrutura matemática conhecida como grafo é amplamente usada na definição de diversos problemas desse tipo, sendo que dentre eles temos os problemas de coloração de grafos, que têm por objetivo encontrar uma determinada rotulação dos vértices de um grafo. Problemas de coloração de grafos são muito importantes pois modelam situações em que há conflitos entre objetos e deseja-se separá-los em grupos de acordo com algum critério, como é o caso em problemas de alocação por exemplo. O objetivo desse projeto é ampliar a experiência do aluno com pesquisa nas áreas de otimização combinatória e projeto de algoritmos por meio do estudo de diferentes problemas de coloração de grafos e seus algoritmos.