Grafos pfaffian - algoritmos.

• Processo: 04/04589-0
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2004
• Data de Término da vigência: 28 de fevereiro de 2006
• Á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: Alberto Alexandre Assis Miranda
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Algoritmos Em Grafos | Grafos Pfaffian | Teoria Dos Grafos

Resumo

Este projeto visa o entendimento das propriedades fundamentais de grafos Pfaffian. Os grafos Pfaffian são precisamente os grafos cujas matrizes de adjacência simétricas tem o seu determinante igual ao quadrado do número de emparelhamentos perfeitos do grafo. Não se conhece nenhuma caracterização para grafos Pfaffian em geral. Sequer se sabe se o problema de determinar se um dado grafo é Pfaffian ou não está em NP ou em co-NP. Entretanto, o problema é solúvel em tempo polinomial quando é feita a restrição a grafos bipartidos. A caracterização de grafos Pfaffian bipartidos foi demonstrada por Little há quase trinta anos. No entanto, somente nos últimos anos surgiram algoritmos polinomiais para a solução da questão, por Robertson et al., e, independentemente, por McCuaig. Nosso objetivo é a compreensão e exposição clara desses algoritmos. Em segundo plano, tentaremos obter algoritmos semelhantes para a classe dos grafos quase-bipartidos, recentemente caracterizada por Little. (AU)

Publicações acadêmicas

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

MIRANDA, Alberto Alexandre Assis. Orientações pfaffianas e o furtivo grafo de Heawood. 2006. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.