Pfaffian graphs and related problems / Grafos pfaffianos e problemas relacionados

AUTOR(ES)

Alberto Alexandre Assis Miranda

DATA DE PUBLICAÇÃO

2009

RESUMO

A área de grafos Pfaffianos apresenta muitos problemas em aberto. Nesta tese resolvemos dois problemas sobre grafos Pfaffianos. O primeiro problema resolvido é a obtenção de um algoritmo polinomial para reconhecimento de grafos quase-bipartidos Pfaffianos. Além disso, estendemos tanto o algoritmo como a caracterização de grafos quase-bipartidos Pfaffianos para a classe dos grafos meio-bipartidos. O segundo resultado é a obtencão de vários resultados estruturais básicos sobre grafos k-Pfaffianos. Utilizando esses resultados, obtivemos um contra-exemplo para a conjectura de Norine, que afirma que o número Pfaffiano de todo grafo é uma potência de quatro: apresentamos um grafo cujo numero Pfaffiano é 6

ASSUNTO(S)

teoria da computação teoria dos casamentos teoria dos grafos matching theory graph theory theory of computation

Documentos Relacionados

• Problemas em grafos com poucos P4 s em grafos indiferença
• Algoritmos para problemas de grafos com incertezas
• Algorithms for classification and partitioning in graphs
• Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos
• Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos