کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142837 | 957166 | 2009 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An edge-reduction algorithm for the vertex cover problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
An approximation algorithm for the vertex cover problem is proposed with performance ratio 32 on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S1S1 such that |S1|≤32|S∗|+ξ where S∗S∗ is an optimal cover and ξξ is an error bound identified.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 37, Issue 3, May 2009, Pages 181–186
Journal: Operations Research Letters - Volume 37, Issue 3, May 2009, Pages 181–186
نویسندگان
Qiaoming Han, Abraham P. Punnen, Yinyu Ye,