A 14$k$-Kernel for Planar Feedback Vertex Set via Region Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
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.
Fichier principal
Vignette du fichier
1410.8336.pdf (615.46 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

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: International Symposium on Parameterized and Exact Computation, Sep 2014, Wroclaw, Poland. pp.97-109, ⟨10.1007/978-3-319-13524-3_9⟩. ⟨lirmm-01264417⟩
160 View
73 Download

Altmetric

Share

Gmail Facebook X LinkedIn More