Abstract

A dynamic kernelisation for d-hitting set with parameter k named lazy sunflower is presented that achieves an update time O(d2 d! kd) for insertion and O(d3 d! kd) for deletions which significantly improves the best bounds known so far.

Original languageEnglish
Pages69-72
Number of pages4
Publication statusPublished - 2019
Event17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization
- University of Twente, Enschede, Netherlands
Duration: 01.07.201903.07.2019
Conference number: 159391

Conference

Conference17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization
Abbreviated titleCTW 2019
Country/TerritoryNetherlands
CityEnschede
Period01.07.1903.07.19

DFG Research Classification Scheme

  • 409-01 Theoretical Computer Science

Cite this