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

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

Marthe Bonamy
Algorithmes, Graphes et Combinatoire
Lukasz Kowalik
  • Fonction : Auteur
Faculty of Mathematics, Informatics, and Mechanics [Warsaw]

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.

Domaines

Mathématique discrète [cs.DM] Combinatoire [math.CO]
Fichier principal
Vignette du fichier
1410.8336.pdf (615.46 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Alexandre Pinlou  : Connectez-vous pour contacter le contributeur

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264417

Soumis le : mardi 4 février 2020-15:54:22

Dernière modification le : jeudi 14 mars 2024-03:13:16

Archivage à long terme le : mardi 5 mai 2020-17:54:56

Télécharger pour visualiser

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⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER ANR
162 Consultations
75 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More