Refined memorization for vertex cover

Memorization is a technique which allows to speed up exponential recursive algorithms at the cost of an exponential space complexity. This technique already leads to the currently fastest algorithm for fixed-parameter vertex cover, whose time complexity is O(1.2832kk1.5+kn), where n is the number of nodes and k is the size of the vertex cover. Via a refined use of memorization, we obtain an O(1.2759kk1.5+kn) algorithm for the same problem. We moreover show how to further reduce the complexity to O(1.2745kk4+kn).