Advertisement
Published in:
2013 | OriginalPaper | Chapter
Random Methods for Parameterized Problems
Authors : Qilong Feng, Jianxin Wang, Shaohua Li, Jianer Chen
Published in: Computing and Combinatorics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we study the random methods for parameterized problems. For the Parameterized
P
2
-Packing problem, by randomly partitioning the vertices, a randomized parameterized algorithm of running time
O
*
(6.75
k
) is obtained, improving the current best result
O
*
(8
k
). For the Parameterized Co-Path Packing problem, we study the kernel and randomized algorithm for the degree-bounded instance, and then by using the iterative compression technique, a randomized algorithm of running time
O
*
(3
k
) is given for the Parameterized Co-Path Packing problem, improving the current best result
O
*
(3.24
k
).