zbMATH — the first resource for mathematics

Improved parameterized upper bounds for Vertex Cover. (English) Zbl 1132.68421
Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 238-249 (2006).
Summary: 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.
For the entire collection see [Zbl 1114.68008].

68Q25 Analysis of algorithms and problem complexity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI