کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952471 | 1442038 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Scattered packings of cycles
ترجمه فارسی عنوان
بسته بندی های پراکنده از چرخه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بسته بندی چرخه، کرنل کردن، الگوریتم های چند متغیره، ساختارهای منجر شده،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the problem Scattered Cycles which, given a graph G and two positive integers r and â, asks whether G contains a collection of r cycles that are pairwise at distance at least â. This problem generalizes the problem Disjoint Cycles which corresponds to the case â=1. We prove that when parameterized by r, â, and the maximum degree Î, the problem Scattered Cycles admits a kernel on 24â2Îârlogâ¡(8â2Îâr) vertices. We also provide a (16â2Îâ)-kernel for the case r=2 and a (148Îrlogâ¡r)-kernel for the case â=1. Our proofs rely on two simple reduction rules and a careful analysis.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 647, 27 September 2016, Pages 33-42
Journal: Theoretical Computer Science - Volume 647, 27 September 2016, Pages 33-42
نویسندگان
Aistis Atminas, Marcin KamiÅski, Jean-Florent Raymond,