Recently, there have been increasing interests and progresses in lowering the worst case time complexity for well-known NP-hard problems, in particular for hte Vertex Cover problem. In this paper, new properties for the Vertex Cover problem are indicated and several new techniques are introduced, which lead to a simpler and improved algorithm of tiem complexity O(kn +1.271~kk~2) for the problem. Our algorithm also induces improvement on previous algorithms for the Independent Set problem on graphs of small degree.
展开▼
