Grafos pfaffianos e problemas relacionados

• Processo: 05/04426-6
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de setembro de 2006
• Data de Término da vigência: 31 de outubro de 2009
• Á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: Pfaffian | Grafos Cobertos por Emparelhamentos

Resumo

Este projeto visa determinar a classe de complexidade (P, NP, co-NP, NP-completo, etc) de problemas sobre grafos Pfaffianos. Os grafos Pfaffianos são precisamente os grafos cujas arestas podem ser orientadas de tal forma que todo circuito conforme no grafo com um número par de vértices tem orientação ímpar. Não se conhece nenhuma caracterização para grafos Pfaffianos em geral. Sequer se sabe se o problema de determinar se um dado grafo é Pfaffiano 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 Pfaffianos 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 McCuaig e, independentemente, por Robertson, Seymour e Thomas. Além disso, todo grafo planar é Pfaffiano. Estas são as únicas classes de grafos, até hoje, para as quais se conhece algoritmo polinomial que decide se um dado grafo é Pfaffiano. O trabalho de mestrado do candidato envolveu o estudo do algoritmo de reconhecimento de grafos bipartidos Pfaffianos. A dissertação de mestrado do candidato apresenta uma prova de corretude do algoritmo alternativa às duas provas anteriormente conhecidas. Agora no projeto de doutorado, pretende-se pesquisar problemas em aberto sobre grafos Pfaffianos. (AU)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

MIRANDA‚ A.A.A.; LUCCHESI‚ C.L.. Recognizing near-bipartite Pfaffian graphs in polynomial time. DISCRETE APPLIED MATHEMATICS, v. 158, n. 12, p. 1275-1278, 2010. (05/04426-6)

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. Grafos pfaffianos e problemas relacionados. 2009. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.