Details

Autor(en) / Beteiligte

• Feng, Qilong
• Zhuo, Beilin
• Tan, Guanlan
• Huang, Neng
• Wang, Jianxin

Titel

Improved Kernels for Several Problems on Planar Graphs

Ist Teil von

• Frontiers in Algorithmics, p.169-180

Ort / Verlag

Cham: Springer International Publishing

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• In this paper, we study the kernelization of the Induced Matching problem on planar graphs, the Parameterized Planar 4-Cycle Transversal problem and the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem. For the Induced Matching problem on planar graphs, based on Gallai-Edmonds structure, a kernel of size 26k is presented, which improves the current best result 28k. For the Parameterized Planar 4-Cycle Transversal problem, by partitioning the vertices in given instance into four parts and analyzing the size of each part independently, a kernel with at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$51k-22$$\end{document} vertices is obtained, which improves the current best result 74k. Based on the kernelization process of the Parameterized Planar 4-Cycle Transversal problem, a kernel of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$51k-22$$\end{document} can also be obtained for the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem, which improves the current best result 96k.