Improved Parameterized Upper Bounds for Vertex Cover | Zendy

Jianer Chen | Zendy; Iyad Kanj | Zendy; Ge Xia | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Improved Parameterized Upper Bounds for Vertex Cover

Author(s) -

Jianer Chen,

Iyad Kanj,

Ge Xia

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-37791-3

DOI - 10.1007/11821069_21

Subject(s) - parameterized complexity , vertex cover , upper and lower bounds , cover (algebra) , vertex (graph theory) , combinatorics , polynomial , exponential function , space (punctuation) , mathematics , pspace , time complexity , bounded function , computer science , discrete mathematics , algorithm , graph , computational complexity theory , mathematical analysis , mechanical engineering , engineering , operating system

This paper presents an O(1.2738k + kn)-time polynomial-space parameterized algorithm for Vertex Cover improving the previous O(1.286k + kn)-time polynomial-space upper bound by Chen, Kanj, and Jia. The algorithm also improves the O(1.2745kk4 + kn)-time exponential-space upper bound for the problem by Chandran and Grandoni.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research