Campus Event Calendar
Event Entry
What and Who
Enumerating Minimal Transversals of Geometric Hypergraphs
Saurabh Ray
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 27 October 2009
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We consider the problem of enumerating all minimal transversals of a hypergraph. In general, it is not known whether one can enumerate all (inclusion-wise) minimal transversals in output polynomial time. We show that if the hypergraph has a "balanced subdivision", then we can indeed enumerate its minimal transversals in time polynomial in the output size. We finally show that several geometrically induced hypergraphs do have such a balanced subdivision. This gives polynomial time algorithms for them.
Contact
Saurabh Ray
06819325129
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Hitting Sets, Hypergraph Transversals, Discrete Geometry
Saurabh Ray, 10/12/2009 15:09 -- Created document.