Random Methods for Parameterized Problems Conference Paper uri icon

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

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Feng, Q., Wang, J., Li, S., & Chen, J.

citation count

  • 3

complete list of authors

  • Feng, Qilong||Wang, Jianxin||Li, Shaohua||Chen, Jianer

publication date

  • October 2013