New kernels for several problems on planar graphs
type: Item
instance of: scholarly article
title: New kernels for several problems on planar graphs
zbMATH Open document ID: 1436.68263
author: Guanlan Tan
author: Qilong Feng
author: Beilin Zhuo
author: Neng Huang
author: Jianxin Wang
published in: Theoretical Computer Science
publication date: 2020-01-16T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7152281
zbMATH Keywords: kernelization
zbMATH Keywords: induced matching
zbMATH Keywords: Gallai-Edmonds decomposition
zbMATH Keywords: cycle transversal
MaRDI profile type: Publication
full work available at URL: j.tcs.2019.09.024
OpenAlex ID: W2975609250
cites work: Polynomial-time data reduction for dominating set
cites work: Maximum cuts and judicious partitions in graphs without short cycles
cites work: Parameterized computational complexity of Dodgson and Young elections
cites work: On generating triangle-free graphs
cites work: Induced matchings
cites work: Induced matchings in intersection graphs.
cites work: Finding a maximum induced matching in weakly chordal graphs
cites work: Approximating maximum agreement forest on multiple binary trees
cites work: Algorithms – ESA 2004
cites work: Parameterized Algorithms
cites work: Q4393480
cites work: On the approximability of the maximum induced matching problem
cites work: Improved induced matchings in sparse graphs
cites work: Improved PTAS for the constrained \(k\)-means problem
cites work: Kernelization
cites work: Q3139292
cites work: New results on induced matchings
cites work: Approximation and Online Algorithms
cites work: Linear Problem Kernels for NP-Hard Problems on Planar Graphs
cites work: Which Codes Have$4$-Cycle-Free Tanner Graphs?
cites work: Irredundancy in circular arc graphs
cites work: Edge-disjoint packing of stars and cycles
cites work: On the induced matching problem
cites work: Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
cites work: Approximating Maximum Subgraphs without Short Cycles
cites work: On a conjecture of Tuza about packing and covering of triangles
cites work: Matching theory
cites work: On maximum induced matchings in bipartite graphs
cites work: Some results on graphs without long induced paths
cites work: The parameterized complexity of the induced matching problem
cites work: Approximability results for the maximum and minimum maximal induced matching problems
cites work: A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
cites work: NP-completeness of some generalizations of the maximum matching problem
cites work: On the chromatic number of triangle-free graphs of large minimum degree
cites work: On the chromatic number of pentagon-free graphs of large minimum degree
cites work: Kernelization for Cycle Transversal Problems
cites work: On the small cycle transversal of planar graphs
cites work: Node-and edge-deletion NP-complete problems
cites work: Equitable list colorings of planar graphs without short cycles
Wikidata QID: Q127198155
DOI: 10.1016/J.TCS.2019.09.024
description: scientific article