An $$O(|E(G)|^2)$$ algorithm for recognizing Pfaffian graphs of a type of bipartite graphs |
| |
Authors: | Xing Feng Lianzhu Zhang Mingzu Zhang |
| |
Affiliation: | 1.School of Mathematical Science,Xiamen University,Xiamen,China |
| |
Abstract: | A graph (G=(V,E)) with even number vertices is called Pfaffian if it has a Pfaffian orientation, namely it admits an orientation such that the number of edges of any M-alternating cycle which have the same direction as the traversal direction is odd for some perfect matching M of the graph G. In this paper, we obtain a necessary and sufficient condition of Pfaffian graphs in a type of bipartite graphs. Then, we design an (O(|E(G)|^2)) algorithm for recognizing Pfaffian graphs in this class and constructs a Pfaffian orientation if the graph is Pfaffian. The results improve and generalize some known results. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|