کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434289 689713 2014 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Pfaffian orientations for a type of bipartite graph
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Pfaffian orientations for a type of bipartite graph
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 527, 27 March 2014, Pages 97–101
نویسندگان
, , ,