Note: 
(submitted to a journal) 
LaTeX Abstract: 
Let $\cH\subseteq 2^V$ be a hypergraph on vertex set $V$. For a positive integer $r$, we call $\cH$ $r$exact, if
any minimal transversal of $\cH$ intersects any hyperedge of $\cH$ in at most $r$ vertices.
This class includes several interesting examples from geometry, e.g., circulararc hypergraphs ($r=2$), hypergraphs defined by sets of axisparallel 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$). For constant $r$, we give a polynomialtime algorithm for the duality testing problem of a pair of $r$exact hypergraphs. This result implies that minimal hitting sets for the above geometric hypergraphs can be generated in outputsensitive polynomial time. 
Categories / Keywords: 
Transveral hypergraphs, Enumeration problems, Monotone Boolean dualization, Readability, Geometric transversals 
HyperLinks / References / URLs: 

Personal Comments: 

File Upload: 



Download
Access Level: 
Internal 
