Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649143 | Discrete Mathematics | 2010 | 8 Pages |
Abstract
Let H⊆2VH⊆2V be a hypergraph on vertex set VV. For a positive integer rr, we call Hr-exact if any minimal transversal of HH intersects any hyperedge of HH in at most rr vertices. This class includes several interesting examples from geometry, e.g., circular-arc hypergraphs (r=2r=2), hypergraphs defined by sets of axis parallel lines stabbing a given set of αα-fat objects (r=4αr=4α), and hypergraphs defined by sets of points contained in translates of a given cone in the plane (r=2r=2). For constant rr, we give a polynomial-time algorithm for the duality testing problem of a pair of rr-exact hypergraphs. This result implies that minimal hitting sets for the above geometric hypergraphs can be generated in output polynomial time.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Khaled Elbassioni, Imran Rauf,