کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875462 | 1441955 | 2018 | 26 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Dealing with several parameterized problems by random methods
ترجمه فارسی عنوان
کار با چندین مشکل پارامتری با روش های تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we apply random methods to deal with several parameterized problems. For the Parameterized Weighted P3-Packing problem, by randomly partitioning the vertices in given graph, a tripartite graph can be obtained. We prove that the Parameterized Weighted P3-Packing problem can be solved in polynomial time on tripartite graphs. Based on the algorithm on tripartite graphs, a randomized parameterized algorithm of running time Oâ(32k) is given for the Parameterized Weighted P3-Packing problem. For the Parameterized Weighted Load Coloring problem, by randomly partitioning the vertices in given graph into two parts and studying the structure properties of the connected components in two parts, a randomized parameterized algorithm of running time Oâ(11.32k) is presented. For the Parameterized Claw-free Edge Deletion problem on Diamond-free Graphs, by combining random with branching methods, a parameterized algorithm of running time Oâ(2.42k) is given.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 734, 22 July 2018, Pages 94-104
Journal: Theoretical Computer Science - Volume 734, 22 July 2018, Pages 94-104
نویسندگان
Qilong Feng, Neng Huang, Xiong Jiang, Jianxin Wang,