Advanced search
Start date

Pfaffian graphs and related problems

Grant number: 05/04426-6
Support Opportunities:Scholarships in Brazil - Doctorate
Effective date (Start): September 01, 2006
Effective date (End): October 31, 2009
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Cláudio Leonardo Lucchesi
Grantee:Alberto Alexandre Assis Miranda
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil


This project's goal is to define some Pfaffian graphs related problems complexity class (P, NP, co-NP, NP-complete, etc). Pfaffian graphs are the graph whose edges can be oriented such that each conformal circuit with an even number of vertices has an odd orientation. No characterization is known for any Pfaffian graphs. It is not even known whether the problem of determining if a given graph is Pfaffian is in NP or in co-NP. However, the problem has a polynomial time solution when it is restricted to bipartite graphs. The Pfaffian bipartite graph characterization was proved by Little thirty years ago. However, only during the last few years polynomial time algorithms for this problem were discovered, by McCuaig and, independently, by Robertson, Seymour and Thomas. Also, every planar graph is Pfaffian. These are the only graph classes, until today, for which a polynomial time algorithm to decide whether a graph is Pfaffian is known. The work developed during the candidates master included the study of the Pfaffian bipartited graph recognition algorithm. The candidate's master dissertation presents a new correctness proof to the algorithm. This proof is different to the two previously know proofs. Now, during the PhD, open problems about Pfaffian graphs are intended to be researched. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
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, . (05/04426-6)
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
MIRANDA, Alberto Alexandre Assis. Pfaffian graphs and related problems. 2009. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.

Please report errors in scientific publications list using this form.