Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 16, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Patrick Traxler (TU Wien)
In this talk we present the problem of recognizing transversal hypergraphs. Given two hypergraphs G and H, decide if G is the transversal hypergraph of H, symbolically G = Tr(H). The transversal hypergraph Tr(H) of H is the set of all subset-minimal transversals (vertex covers) of H. It is open whether there exists a polynomial time algorithm for this problem. The problem is not known to be complete for NP or coNP. The currently best upper time bound is no(lg(n)). The complementary problem can be solved on a nondeterministic Turing machine with a polylogarithmic amount of nondeterministic bits. We shortly discuss these results and some related problems.
Automatic MiSe System Software Version 1.4803M | admin login