Algoritmos para coloração de grafos

• Processo: 20/09330-7
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Vigência (Início): 01 de novembro de 2020
• Vigência (Término): 31 de maio 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
• Palavra(s)-Chave do Pesquisador: análise de algoritmos | Coloração de grafos | grafos | 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.