Advertisement
Published in:
2006 | OriginalPaper | Chapter
Improved Parameterized Upper Bounds for Vertex Cover
Authors : Jianer Chen, Iyad A. Kanj, Ge Xia
Published in: Mathematical Foundations of Computer Science 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.