Dynamic Meta-Kernelization

2026 Open access

Read full text
Authors: Christian Bertram, Deborah Haun, Mads Vestergaard Jensen, T. Korhonen
DOI: 10.1145/3798129.3800774
Cited by: 0

Abstract

Kernelization studies polynomial-time preprocessing algorithms. Over the last 20 years, the most celebrated positive results of the field have been linear kernels for classical NP-hard graph problems on sparse graph classes. In this paper, we lift these results to the dynamic setting.

Fields of Study & Subjects

Advanced Graph Theory Research Complexity and Algorithms in Graphs Computational Geometry and Mesh Generation

Publication details

Pages
575–583
Publication date
9 June 2026
Language
EN