A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2014

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

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.

Domains

Discrete Mathematics [cs.DM] Combinatorics [math.CO]
Fichier principal
Vignette du fichier
1410.8336.pdf (615.46 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Alexandre Pinlou  : Connect in order to contact the contributor

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

Submitted on : Tuesday, February 4, 2020-3:54:22 PM

Last modification on : Thursday, March 14, 2024-3:13:16 AM

Long-term archiving on : Tuesday, May 5, 2020-5:54:56 PM

Download

Dates and versions

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

Identifiers

Cite

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER ANR
166 View
83 Download

Altmetric

Share

More