New kernels for several problems on planar graphs

DOI10.1016/j.tcs.2019.09.024zbMath1436.68263MaRDI QIDQ2285156

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

Publication date: 16 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.09.024

zbMATH Keywords

induced matching; kernelization; cycle transversal; Gallai-Edmonds decomposition

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q27: Parameterized complexity, tractability and kernelization