AG 1, AG 5   Info

AG Audience

English

30 Minutes

Saarbrücken

A hypergraph is called $r$-exact for an integer $r>0$, if any of its minimal transversal and hyperedge intersect in at most $r$ vertices. We show that the class includes several interesting examples from geometry, e.g., circular-arc hypergraphs ($r=2$), hypergraphs defined by sets of axis-parallel lines stabbing a given set of $\alpha$-fat objects ($r=4\alpha$), and hypergraphs defined by sets of points contained in translates of a given cone in the plane ($r=2$). Finally, for constant $r$, we show that all minimal hitting sets for $r$-exact hypergraphs can be generated in output-sensitive polynomial time.

Imran Rauf

--email hidden

passcode not visible

logged in users only