کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951257 | 1441199 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On a generalization of Nemhauser and Trotter's local optimization theorem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Fellows, Guo, Moser and Niedermeier [14] proved a generalization of Nemhauser and Trotter's theorem, which applies to d-Bounded-Degree Vertex Deletion (to delete k vertices of the input graph to make the maximum degree of it â¤d) and gives a linear-vertex kernel for d=0 and 1, and a superlinear-vertex kernel for each dâ¥2 for the problem parameterized by k. It is still left as an open problem whether this parameterized problem admits a linear-vertex kernel for each dâ¥3. In this paper, we refine the generalized Nemhauser and Trotter's theorem and give a linear-vertex kernel for each dâ¥0.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 84, March 2017, Pages 97-106
Journal: Journal of Computer and System Sciences - Volume 84, March 2017, Pages 97-106
نویسندگان
Mingyu Xiao,