Grafos Pfaffianos e Problemas Relacionados
Resumo
A área de grafos Pfaffianos apresenta muitos problemas em aberto. Na tese descrita aqui 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 obtençã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 número Pfaffiano é 6.Referências
Ben-Dor, A. and Halevi, S. (1995). Zero-one permanent is P-complete, a simpler proof. In Proc. 2nd Israel Symposium on Theory of Computing and Systems (ISTCS93), IEEE. press.
Fischer, I. and Little, C. H. C. (2001). A characterisation of Pfaffian near bipartite graphs. J. Combin. Theory Ser. B, 82:175–222.
Galluccio, A. and Loebl, M. (1999). On the theory of Pfaffian orientations. I. Perfect matchings and permanents. Eletron. J. Combin. , 6.
Harary, F., editor (1967). Graph Theory and Theoretical Physics. Academic Press Inc.
McCuaig, W. (2004). Pólya’s permanent problem. The Electronic J. of Combin., 11.
Miranda, A. A. A. (2009). Grafos Pfaffianos e Problemas Relacionados. PhD thesis, Instituto de Computação - UNICAMP.
Miranda, A. A. A. and Lucchesi, C. L. (2004). Pfaffian graphs. Technical report, Institute of Computing - University of Campinas - UNICAMP.
Miranda, A. A. A. and Lucchesi, C. L. (2008). A polynomial time algorithm for recognizing near-bipartite Pfaffian graphs. Electronic Notes in Discrete Mathematics, 30:171–176. IV Latin-American Algorithms, Graphs and Optimization Symposium - LAGOS 2007, Chile.
Miranda, A. A. A. and Lucchesi, C. L. (2009a). On the pfaffian number of graphs. Electronic Notes in Discrete Mathematics, 35:145 – 150. LAGOS’09 - V Latin-American Algorithms, Graphs and Optimization Symposium.
Miranda, A. A. A. and Lucchesi, C. L. (2009b). Recognizing near-bipartite Pfaffian graphs in polynomial time. Discrete Applied Mathematics.
Muir, T. (1882). A Treatise on the Theory of Determinants. MacMillian and Co., London.
Norine, S. (2009). Drawing 4-Pfaffian graphs on the torus. Combinatorica, 29(1):109 – 119.
Robertson, N., Seymour, P. D., and Thomas, R. (1999). Permanents, Pfaffian orientations and even directed circuits. Ann. of Math. (2), 150:929–975.
Tesler, G. (2000). Matchings in graphs on non-orientable surfaces. J. Combin. Theory Ser. B, 78:198–231.
Tutte, W. T. (1947). The factorization of linear graphs. J. London Math. Soc., 22:107–111.
Tutte, W. T. (1998). Graph Theory as I Have Known It. Number 11 in Oxford Lecture Series in Mathematics and its Applications. Clarendon Press, Oxford.
Valiant, L. G. (1979). The complexity of computing the permanent. Theoretical Computer Science.
Fischer, I. and Little, C. H. C. (2001). A characterisation of Pfaffian near bipartite graphs. J. Combin. Theory Ser. B, 82:175–222.
Galluccio, A. and Loebl, M. (1999). On the theory of Pfaffian orientations. I. Perfect matchings and permanents. Eletron. J. Combin. , 6.
Harary, F., editor (1967). Graph Theory and Theoretical Physics. Academic Press Inc.
McCuaig, W. (2004). Pólya’s permanent problem. The Electronic J. of Combin., 11.
Miranda, A. A. A. (2009). Grafos Pfaffianos e Problemas Relacionados. PhD thesis, Instituto de Computação - UNICAMP.
Miranda, A. A. A. and Lucchesi, C. L. (2004). Pfaffian graphs. Technical report, Institute of Computing - University of Campinas - UNICAMP.
Miranda, A. A. A. and Lucchesi, C. L. (2008). A polynomial time algorithm for recognizing near-bipartite Pfaffian graphs. Electronic Notes in Discrete Mathematics, 30:171–176. IV Latin-American Algorithms, Graphs and Optimization Symposium - LAGOS 2007, Chile.
Miranda, A. A. A. and Lucchesi, C. L. (2009a). On the pfaffian number of graphs. Electronic Notes in Discrete Mathematics, 35:145 – 150. LAGOS’09 - V Latin-American Algorithms, Graphs and Optimization Symposium.
Miranda, A. A. A. and Lucchesi, C. L. (2009b). Recognizing near-bipartite Pfaffian graphs in polynomial time. Discrete Applied Mathematics.
Muir, T. (1882). A Treatise on the Theory of Determinants. MacMillian and Co., London.
Norine, S. (2009). Drawing 4-Pfaffian graphs on the torus. Combinatorica, 29(1):109 – 119.
Robertson, N., Seymour, P. D., and Thomas, R. (1999). Permanents, Pfaffian orientations and even directed circuits. Ann. of Math. (2), 150:929–975.
Tesler, G. (2000). Matchings in graphs on non-orientable surfaces. J. Combin. Theory Ser. B, 78:198–231.
Tutte, W. T. (1947). The factorization of linear graphs. J. London Math. Soc., 22:107–111.
Tutte, W. T. (1998). Graph Theory as I Have Known It. Number 11 in Oxford Lecture Series in Mathematics and its Applications. Clarendon Press, Oxford.
Valiant, L. G. (1979). The complexity of computing the permanent. Theoretical Computer Science.
Publicado
20/07/2010
Como Citar
MIRANDA, Alberto Alexandre Assis; LUCCHESI, Cláudio Leonardo.
Grafos Pfaffianos e Problemas Relacionados. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 23. , 2010, Belo Horizonte/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2010
.
p. 105-112.
ISSN 2763-8820.
