Grafos Pfaffianos: Propriedades e Algoritmos

• Processo: 24/02636-4
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de novembro de 2024
• Data de Término da vigência: 31 de julho de 2026
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cláudio Leonardo Lucchesi
• Beneficiário: Guillermo Enrique Junchaya Heredia
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Palavra(s)-Chave do Pesquisador: Algoritmos para grafos Pfaffianos | Contagem Eficiente de Emparelhamentos Perfeitos | Grafos Pfaffianos - Conjecturas e Resultados | Combinatória e Complexidade de Algoritmos

Resumo

O assunto, Grafos Pfaffianos, é muito rico em aplicações, as mais importantes são em econometria e no estudo de compostos orgânicosestáveis. Do ponto de vista teórico o assunto também é muito atraente, com muitos algoritmos interessantes e problemas em aberto.Por exemplo, até hoje somente se tem caracterizações de grafos Pfaffianos e algoritmos eficientes de reconhecimento para grafos bipartidos e para grafos quase-bipartidos. O objetivo da dissertação de mestrado é apresentar o estado da arte a respeito, com a descrição de teoremas e os correspondentes algoritmos eficientes, além da citação de algumas aplicações mais importantes.