Random Methods for Parameterized Problems
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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 ). 2013 Springer-Verlag Berlin Heidelberg.
name of conference
Computing and Combinatorics, 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings