Pfaffian orientations for a type of bipartite graph
Pfaffian orientations for a type of bipartite graph
复制标题
一类二分图的普法夫方向
DOI：
10.1016/j.tcs.2014.01.030
复制
发表时间：
2014-03
影响因子：
1.1
通讯作者：
卢福良
中科院分区：
文献类型：
--
作者：
林峰根;张莲珠;卢福良
如果图 G−V (C) 具有完美匹配，则图 G 的偶循环 C 是很好的。如果 G 的每个良好循环都有奇数个指向循环任一方向的边，则 G 的方向是普法夫方向。如果图具有普法夫方向，则该图是普法夫图。如果一个图是普法夫图，那么它的完美匹配数可以在多项式时间内计算出来。在本文中，我们关注一种特殊类型的 1-可扩展二分图，其最大度为 Δ (G)=| V(G)|/2。我们描述了这种类型的普法夫图的一些属性。根据这些性质，我们找到了一个算法，时间为O(|E(G)|2)来判断该类型的图G是否是普法夫图。此外，如果G是Pfaffian，该算法还构造它的Pfaffian方向。
An even cycle C of a graph G is nice if the graph 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. We characterize some properties of Pfaffian graphs in this type. According to the properties, we find an algorithm in time 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.
登录
查看更多内容
DOI：
10.1016/j.jctb.2007.12.005
发表时间：
2008-09
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Sergey Norin;R. Thomas
通讯作者：
Sergey Norin;R. Thomas
DOI：
10.1016/0095-8956(75)90048-9
发表时间：
1975-06
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
C. Little
通讯作者：
C. Little
DOI：
10.1137/0202012
发表时间：
1973-09
期刊：
SIAM J. Comput.
影响因子：
--
作者：
J. Hopcroft;R. Tarjan
通讯作者：
J. Hopcroft;R. Tarjan
DOI：
--
发表时间：
2010
期刊：
--
影响因子：
--
作者：
B. Alom;Someresh Das;Md. Saiful Islam
通讯作者：
B. Alom;Someresh Das;Md. Saiful Islam
DOI：
10.1017/s1446788700032730
发表时间：
1991-04
期刊：
Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics
影响因子：
--
作者：
C. Little;F. Rendl
通讯作者：
C. Little;F. Rendl