CAJ | 학술논문

关于一般的图的完美匹配计数的问题已证实是NP-hard问题.但Pfaffian图的完美匹配计数问题(以及其它相关问题)却能够在多项式时间内解决.由此可见图的Pfaffian性的重要性.在这篇文章中,我们研究了若干种影响图的Pfaffian性的运算.
관우일반적도적완미필배계수적문제이증실시NP-hard문제.단Pfaffian도적완미필배계수문제(이급기타상관문제)각능구재다항식시간내해결.유차가견도적Pfaffian성적중요성.재저편문장중,아문연구료약간충영향도적Pfaffian성적운산.
It is well known that enumeration problem of perfect matchings for general graphs is NP-hard. The importance of Pfaffian orientations stems from the fact that if a graph G is Pfaffian,then the number of perfect matchings of G (as well as other related problems) can be computed in polynomial time. In the present paper, we DISCUSS some operations on graphs and examine their effect on the Pfaffian property of graphs.