A kernel of order 2k-c log k for vertex cover
In a recent paper Soleimanfallah and Yeo proposed a kernelization algorithm for vertex cover which, for any fixed constant c, produces a kernel of order 2k - c in polynomial time. In this paper we show how their techniques can be extended to improve the produced kernel to order 2k - c log k, for any fixed constant c. (C) 2011 Elsevier B.V. All rights reserved.
vertex cover kernelization algorithm graph algorithms parameterized complexity