Counting the Number of Perfect Matchings in K5-free Graphs

被引：9

作者：

Straub, Simon ^{[1
]}

Thierauf, Thomas ^{[2
]}

Wagner, Fabian ^{[1
]}

机构：

[1] Univ Ulm, Theoret Comp Sci, D-89069 Ulm, Germany

[2] Aalen Univ, Dept Elect & Informat, D-73430 Aalen, Germany

来源：

2014 IEEE 29TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC) | 2014年

关键词：

counting; perfect matchings; K-5-free graphs; ALGORITHM;

D O I：

10.1109/CCC.2014.15

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Counting the number of perfect matchings in arbitrary graphs is a #P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for K-3,K-3-free graphs, Vazirani showed that it is in NC2. The technique there is to compute a Pfaffian orientation of a graph. In the case of K-5-free graphs, this technique will not work because some K-5-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K-5-free graphs can be computed in polynomial time and we describe a circuit construction in TC2.

引用

页码：66 / 77

页数：12

共 22 条

[1]

Battista G. D., 1989, IEEE S FDN COMP SCI, P436

[2]

Datta S., 2009, P 29 ANN C FDN SOFTW, V4, P145

[3] Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs [J].

Datta, Samir ;

Kulkarni, Raghav ;

Roy, Sambuddha .

THEORY OF COMPUTING SYSTEMS, 2010, 47 (03) :737-757

[4] Planar Graph Isomorphism is in Log-Space [J].

Datta, Samir ;

Limaye, Nutan ;

Nimbhorkar, Prajakta ;

Thierauf, Thomas ;

Wagner, Fabian .

PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, 2009, :203-+

[5] On-line maintenance of triconnected components with SPQR-trees [J].

DiBattista, G ;

Tamassia, R .

ALGORITHMICA, 1996, 15 (04) :302-318

[6] PATHS TREES AND FLOWERS [J].

EDMONDS, J .

CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03) :449-&

[7]

Harary F., 1969, Graph Theory

[8]

Hopcroft J. E., 1973, Journal of Computer and System Sciences, V7, P323, DOI 10.1016/S0022-0000(73)80013-3

[9]

Kasteleyn Pieter, 1967, Graph Theory and Theoretical Physics, P43

[10]

Little C. H. C., 1974, Proceedings of the 2nd Australian Conference on Combinatorial Mathematics, P63, DOI 10.1007/BFb0057377

← 1 2 3 →