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

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