Improved Parameterized Upper Bounds for Vertex Cover

Abstract This paper presents an O (1. 2738 k + kn )-time polynomial-space parameterized algorithm for Vertex Cover improving the previous O (1. 286 k + kn )-time polynomial-space upper bound by Chen, Kanj, and Jia. The algorithm also improves the O (1. 2745 k k 4 + kn )-time exponential-space upper bound for the problem by Chandran and Grandoni.

Authors

• Jianer Chen
• Iyad A. Kanj
• Ge Xia

Keywords

No keywords are indexed for this paper.