کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427041 | 686427 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths
ترجمه فارسی عنوان
هسته خطی ـ گردشی برای مشکل بسته بندی r-stars در یک گراف بدون مسیرهای القا شده طولانی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های گراف؛ بسته بندی؛ ستاره ها؛ هسته؛ ردیابی ثابت پارامتر
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
• Packing r-stars in a graph with no long induced paths.
• Parameter is the number k of r-stars.
• Linear-vertex kernel.
• Conjecture for the general case.
Let integers r≥2r≥2 and d≥3d≥3 be fixed. Let GdGd be the set of graphs with no induced path on d vertices. We study the problem of packing k vertex-disjoint copies of K1,rK1,r (k≥2k≥2) into a graph G from parameterized preprocessing, i.e., kernelization, point of view. We show that every graph G∈GdG∈Gd can be reduced, in polynomial time, to a graph G′∈GdG′∈Gd with O(k)O(k) vertices such that G has at least k vertex-disjoint copies of K1,rK1,r if and only if G′G′ has. Such a result is known for arbitrary graphs G when r=2r=2 and we conjecture that it holds for every r≥2r≥2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 6, June 2016, Pages 433–436
Journal: Information Processing Letters - Volume 116, Issue 6, June 2016, Pages 433–436
نویسندگان
Florian Barbero, Gregory Gutin, Mark Jones, Bin Sheng, Anders Yeo,