کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434289 | 689713 | 2014 | 5 صفحه PDF | دانلود رایگان |

An even cycle C of a graph G is nice if the graph G−V(C)G−V(C) has a perfect matching. An orientation of G is a Pfaffian orientation if every nice cycle of G has an odd number of edges directed in either direction of the cycle. A graph is Pfaffian if it has a Pfaffian orientation. If a graph is Pfaffian, then the number of perfect matchings of it can be computed in polynomial time. In this paper, we focus on a special type of 1-extendable bipartite graph with maximum degree Δ(G)=|V(G)|/2Δ(G)=|V(G)|/2. We characterize some properties of Pfaffian graphs in this type. According to the properties, we find an algorithm in time O(|E(G)|2)O(|E(G)|2) to determine whether a graph G in this type is Pfaffian or not. Furthermore, if G is Pfaffian, this algorithm also constructs a Pfaffian orientation of it.
Journal: Theoretical Computer Science - Volume 527, 27 March 2014, Pages 97–101