zbMATH — the first resource for mathematics

Vertex cover: Further observations and further improvements. (English) Zbl 1017.68087
Summary: Recently, there has been increasing interest and progress in lowering worst-case time complexity for well-known NP-hard problems, particularly for thr VERTEX COVER problem. In this paper, new properties for the VERTEX COVER problem are indicated, and several simple and new techniques are introduced, which lead to an improved algorithm of time \(O(kn+ 1.2852^k)\) for the problem. Our algorithm also induces improvement on previous algorithms for the INDEPENDENT SET problem on graphs of small degree.

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI