Teoria de Kernels em dígrafos

• Processo: 18/16720-6
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2019
• Data de Término da vigência: 30 de setembro de 2019
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Orlando Lee
• Beneficiário: Alonso Ali Gonçalves
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Dígrafos Teoria dos grafos Teoria dos jogos
• Palavra(s)-Chave do Pesquisador: digrafo | kernel | kernel perfeito | k-kernel | Teoria de grafos

Resumo

Neste projeto de pesquisa de mestrado, propomos o estudo de kernels e sua generalização em k-kernels. Inicialmente apresentamos um levantamento do estado da área - identificando os principais resultados e problemas abertos - a fim de compreender com maior profundidade os conceitos estudados e, portanto, alcançar os objetivos com maior facilidade. Kernels em dígrafos nasceram a partir da área de teoria de jogos e obtiveram maior relevância quando foi provada sua relação com grafos perfeitos pelo resultado do Teorema Forte de Grafos Perfeitos. O objetivo desse projeto é o estudo de resultados já existentes sobre a existência de kernels e kernel perfeição em dígrafos e generalizá-los para k-kernel. A generalização de resultados de kernels para k-kernels ganhou reconhecimento após a generalização do Teorema de Richardson -- teorema fundamental na teoria de kernels -- e se mostrou uma linha de estudos frutífera, sendo fortemente estudada nos últimos vinte anos. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

GONÇALVES, Alonso Ali. Sobre circuitos, cordas e kernels em digrafos. 2019. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.