Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875462 | Theoretical Computer Science | 2018 | 26 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Qilong Feng, Neng Huang, Xiong Jiang, Jianxin Wang,