کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951164 1441195 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Linear kernels for separating a graph into components of bounded size
ترجمه فارسی عنوان
هسته های خطی برای جدا کردن یک گراف به اجزای اندازه محدود
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The p-Size Separator problem is to check whether we can delete at most k vertices in a given graph such that each connected component of the remaining graph has at most p vertices. We prove a kernel of O(pk) vertices for this problem, i.e., a linear vertex kernel for each fixed p≥1. Our proofs are based on extremal combinatorial arguments and the main result can be regarded as a generalization of the Nemhauser and Trotter's theorem for the Vertex Cover problem. Our techniques are possible to be used to improve kernel algorithms based on the expansion lemma or crown decompositions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 88, September 2017, Pages 260-270
نویسندگان
,