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:









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

Abstract, Links, ©

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)},
}


Entry last modified by Anja Becker, 03/04/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Imran Rauf
Created
03/06/2009 03:02:19 PM
Revision
1.
0.


Editor
Anja Becker
Imran Rauf


Edit Date
04.03.2010 17:13:19
03/06/2009 03:02:19 PM