کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949946 | 1440207 | 2016 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Kernelization of edge perfect code and its variants
ترجمه فارسی عنوان
کرنل کردن کد کامل لبه و انواع آن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی پارامتریک، کرنل کردن، کد کامل،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that the three problems Edge Perfect Code, Edge Weakly-Perfect Code, and Edge Semi-Perfect Code  are all fixed-parameter tractable (with the solution size k as parameter) by obtaining various kernelization results. In general graphs, Edge Perfect Code  admits a problem kernel with O(k2) vertices and O(k3) edges, Edge Weakly-Perfect Code  admits a problem kernel with O(k3) vertices and O(k3) edges, and Edge Semi-Perfect Code  admits a problem kernel with O(2kâ
k) vertices and O(2kâ
k) edges. In planar graphs and in graphs without small cycles or large stars, the kernel sizes for the three problems can be significantly reduced, to O(k2) and in some cases even to O(k). On the other hand, all three problems remain NP-complete in grid graphs of maximum degree 3 and arbitrarily large girth. Moreover, Edge Semi-Perfect Code  does not admit any polynomial kernel in bipartite graphs unless NP â coNP/poly.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 214, 11 December 2016, Pages 145-152
Journal: Discrete Applied Mathematics - Volume 214, 11 December 2016, Pages 145-152
نویسندگان
Minghui Jiang, Yong Zhang,