| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4648474 | Discrete Mathematics | 2011 | 4 Pages |
Abstract
The best known kernel for the vertex cover problem was of order 2k2k for a long time, by a result of Chen et al. Recently, results by Chlebík and Clebíková, have implied that this can be improved to 2k−12k−1. In this paper, we provide a new structural result which can be used to improve this to 2k−c2k−c, for any constant cc.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Arezou Soleimanfallah, Anders Yeo,