Unpublished, Draft, To Appear @UnPublished Unveröffentlicht, Entwurf

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Elbassioni, Khaled Rauf, Imran dblp dblp
 BibTeX citekey*: ElbRau09a

 Title, Booktitle
 Title*: Polynomial-time Dualization of $r$-Exact Hypergraphs with Applications in Geometry

 Vol, No, pp., Year
 Month: March Year: 2010 Language: English Pages: 12

 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., 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$). For constant $r$, we give a polynomial-time 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 output-sensitive 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

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: Fachbeirat

BibTeX Entry:
@UNPUBLISHED{ElbRau09a,
AUTHOR = {Elbassioni, Khaled and Rauf, Imran},
TITLE = {Polynomial-time Dualization of $r$-Exact Hypergraphs with Applications in Geometry},
YEAR = {2010},
PAGES = {12},
MONTH = {March},
NOTE = {(submitted to a journal)},
}