A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2014

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.
Fichier principal
Vignette du fichier
1410.8336.pdf (615.46 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01264417 , version 1 (04-02-2020)

Identifiants

Citer

Marthe Bonamy, Lukasz Kowalik. A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition. IPEC 2014 - 9th International Symposium on Parameterized and Exact Computation, Sep 2014, Wroclaw, Poland. pp.97-109, ⟨10.1007/978-3-319-13524-3_9⟩. ⟨lirmm-01264417⟩
172 Consultations
85 Téléchargements

Altmetric

Partager

More