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

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
نویسندگان
, , ,