| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6875415 | Theoretical Computer Science | 2018 | 6 Pages |
Abstract
We revisit crown decomposition for the Vertex Cover problem by giving a simple 2k-kernelization algorithm. Previously, a 2k kernel was known but it was computed using both crown decomposition and linear programming; moreover, with crown decomposition alone only a 3k kernel was known. Our refined crown decomposition carries some extra property and could be used for some other related problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wenjun Li, Binhai Zhu,