Minimal hypergraph transversals and their use in Computer Science

Seminar series

Combinatorial Theory Seminar

Date

Tue, 20 Nov 2007
13:30

Location

Speaker

Georg Gottlob

Organisation

Oxford

Hypergraph Transversals have been studied in Mathematics for a long time (e.g. by Berge) . Generating minimal transversals of a hypergraph is an important problem which has many applications in Computer Science, especially in database Theory, Logic, and AI. We give a survey of various applications and review some recent results on the complexity of computing all minimal transversals of a given hypergraph.