Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with $K_5$-free graphs:
TR14-079 | 11th June 2014
Simon Straub, Thomas Thierauf, Fabian Wagner

Counting the Number of Perfect Matchings in $K_5$-free Graphs

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,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>

ISSN 1433-8092 | Imprint