A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition
Résumé
We show a kernel of at most 14k vertices for the Planar Feedback Vertex Set problem. This improves over the previous kernel of size bounded by 97k. Our algorithm has a few new reduction rules. However, our main contribution is an application of the region decomposition technique in the analysis of the kernel size.
Origine | Fichiers produits par l'(les) auteur(s) |
---|
Loading...