A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition

Marthe Bonamy; Lukasz Kowalik

doi:10.1007/978-3-319-13524-3_9

Retour

A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition

Acte de colloque

Open Access

A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition

Marthe Bonamy et Lukasz Kowalik

Revised Selected Papers, Vol.LNCS(8894), pp.97-109

Revised Selected Papers

IPEC 2014 - 9th International Symposium on Parameterized and Exact Computation (Wroclaw, Poland, 10/09/2014–12/09/2014)

2014

DOI: https://doi.org/10.1007/978-3-319-13524-3_9

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.

Fichiers et liens (1)

url

Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Titre: A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition
Créateurs - sans rôle: Marthe Bonamy - Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
Lukasz Kowalik - Faculty
Détails de publication: Revised Selected Papers, Vol.LNCS(8894), pp.97-109
Colloque: IPEC 2014 - 9th International Symposium on Parameterized and Exact Computation (Wroclaw, Poland, 10/09/2014–12/09/2014)
Publications en série: Revised Selected Papers
Identifiants: 9938541209311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Langue: English
Type de ressource: Conference proceeding
Champs locaux: lirmm-01264417