کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10523854 | 957103 | 2005 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On approximation of the vertex cover problem in hypergraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
This paper deals with approximation of the vertex cover problem in hypergraphs with bounded degree and bounded number of neighboring vertices. For hypergraphs with edges of size at most r and degree bounded by Î we extend a result of Krivelevich and obtain a âβrâ approximation algorithm, where 0<β<1 satisfies 1-β=[βr/(βr+1)]Î-1/βr. In particular, we show that when (logÎ)/r⩾1-1/e the approximation guarantee of our algorithm is better than that of the greedy algorithm. For hypergraphs in which each vertex has at most D adjacent vertices and its degree is bounded by Î⩾D, we show that the greedy heuristic provides an H(Î,D)⩽(D-1)[1-Î1/(1-D)]+1 approximation, which in some cases significantly improves the well known H(Î)⩽logÎ+1 bound.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 2, Issue 1, 30 March 2005, Pages 101-111
Journal: Discrete Optimization - Volume 2, Issue 1, 30 March 2005, Pages 101-111
نویسندگان
Michael Okun,