Improved parameterized upper bounds for vertex cover Conference Paper

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^kk⁴ + kn)-time exponential-space upper bound for the problem by Chandran and Grandoni. Springer-Verlag Berlin Heidelberg 2006.

name of conference

• Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Star Lesn, Slovakia, August 28-September 1, 2006, Proceedings
• Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings

authors

• Chen, Jianer

published proceedings

• MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2006, PROCEEDINGS

author list (cited authors)

• Chen, J., Kanj, I. A., & Xia, G. e.

complete list of authors

• Chen, Jianer||Kanj, Iyad A||Xia, Ge

publication date

• January 2006

published in

• Lecture Notes in Artificial Intelligence  Journal

International Standard Book Number (ISBN) 10

• 3-540-37791-3

International Standard Book Number (ISBN) 13

• 9783540377917

start page

• 238

end page

• 249

volume

• 4162