An O(|E(G)|2) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs

报告题目:  An O(|E(G)|2) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs

 报  告  人:张莲珠    教授(厦门大学)

 报告时间:2017年10月26日(星期四)下午16:20

 报告地点:第三办公区202室


 报告摘要:

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.

 

报告人介绍:

现任厦门大学教授,博士生导师,中国运筹学会图论与组合分会常务理事,享受国务院政府津贴专家。主要研究兴趣是图论及其应用。主持或参与多项国家自然科学基金项目和重点项目,已在知名学术期刊发表论文50余篇,部分研究成果曾获省部级科学技术奖。