Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SIMON STRAUB:
All reports by Author Simon Straub:

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 >>>


TR11-148 | 3rd November 2011
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf

Planarizing Gadgets for Perfect Matching do not Exist

To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem.
The obvious way to construct such a reduction is via a {\em planarizing ... more >>>




ISSN 1433-8092 | Imprint