Quadratic vertex kernel for split vertex deletion

DOI10.1007/978-3-030-17402-6_1zbMath1489.68179MaRDI QIDQ5919394

R. Krithika, Sushmita Gupta, Akanksha Agrawal, Pallavi Jain

Publication date: 6 February 2020

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-17402-6_1

zbMATH Keywords

parameterized complexity; kernelization; split vertex deletion; kernel lower bound

Mathematics Subject Classification ID

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

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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q27: Parameterized complexity, tractability and kernelization