Sobre circuitos, cordas e kernels em digrafos

Autor(es)

Alonso Ali Gonçalves

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2019-09-17

Membros da banca

Orlando Lee; Christiane Neme Campos; Maycon Sambinelli

• Orientador: Orlando Lee

Resumo

Um kernel é um subconjunto de vértices independentes e absorventes em um digrafo. O conceito de kernel foi introduzido por von Neumann e Morgenstern no contexto de teoria de jogos com o intuito de modelar interações econômicas e sociais. O conceito ganhou notoriedade no campo de teoria de grafos por conta de sua relação com a Conjectura de Grafos Perfeitos (agora Teorema Forte dos Grafos Perfeitos) e sua aplicabilidade para encontrar estratégias ganhadoras em jogos. Nesta dissertação, damos continuidade ao estudo de condições suficientes para a existência de kernels e k-kernels em digrafos cujos circuitos possuem cordas. Apresentamos os principais resultados da área, assim como novos problemas e resultados obtidos ao longo da pesquisa do mestrado (AU)

• Processo FAPESP: 18/16720-6 - Teoria de Kernels em dígrafos
• Beneficiário: Alonso Ali Gonçalves
• Modalidade de apoio: Bolsas no Brasil - Mestrado