Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jochen Messner:

TR13-112 | 12th August 2013
Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf

Exact Perfect Matching in Complete Graphs

A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges.

We show that for complete and bipartite complete graphs, the exact perfect ... 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 >>>

TR11-018 | 8th February 2011
Jochen Messner, Thomas Thierauf

A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability

Recently, Moser and Tardos [MT10] came up with a constructive proof of the Lovász Local Lemma. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve the Local Lemma slightly.

more >>>

ISSN 1433-8092 | Imprint