کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649143 | 1632435 | 2010 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial-time dualization of rr-exact hypergraphs with applications in geometry
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issues 17–18, 28 September 2010, Pages 2356–2363
Journal: Discrete Mathematics - Volume 310, Issues 17–18, 28 September 2010, Pages 2356–2363
نویسندگان
Khaled Elbassioni, Imran Rauf,