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

Marthe Bonamy 1 Lukasz Kowalik 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Communication dans un congrès
IPEC: International Symposium on Parameterized and Exact Computation, 2014, Wroclaw, Poland. 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers, LNCS (8894), pp.97-109, 2014, Parameterized and Exact Computation. 〈10.1007/978-3-319-13524-3_9〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264417
Contributeur : Alexandre Pinlou <>
Soumis le : vendredi 29 janvier 2016 - 11:57:04
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

Collections

Citation

Marthe Bonamy, Lukasz Kowalik. A 14k-Kernel for Planar Feedback Vertex Set via Region Decomposition. IPEC: International Symposium on Parameterized and Exact Computation, 2014, Wroclaw, Poland. 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers, LNCS (8894), pp.97-109, 2014, Parameterized and Exact Computation. 〈10.1007/978-3-319-13524-3_9〉. 〈lirmm-01264417〉

Partager

Métriques

Consultations de la notice

141