ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



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

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