کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648474 | 1632431 | 2011 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A kernel of order 2k−c2k−c for Vertex Cover
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The best known kernel for the vertex cover problem was of order 2k2k for a long time, by a result of Chen et al. Recently, results by Chlebík and Clebíková, have implied that this can be improved to 2k−12k−1. In this paper, we provide a new structural result which can be used to improve this to 2k−c2k−c, for any constant cc.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issues 10–11, 6 June 2011, Pages 892–895
Journal: Discrete Mathematics - Volume 311, Issues 10–11, 6 June 2011, Pages 892–895
نویسندگان
Arezou Soleimanfallah, Anders Yeo,