Improved dynamic kernels for hitting-set

Zacharias Heinrich; Rudiger Reischuk

Improved dynamic kernels for hitting-set

Institute of Theoretical Computer Science

Abstract

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

Original language	English
Pages	69-72
Number of pages	4
Publication status	Published - 2019
Event	17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization - University of Twente, Enschede, Netherlands Duration: 01.07.2019 → 03.07.2019 Conference number: 159391

Conference

Conference	17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization
Abbreviated title	CTW 2019
Country/Territory	Netherlands
City	Enschede
Period	01.07.19 → 03.07.19

DFG Research Classification Scheme

4.43-01 Theoretical Computer Science

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Cite this

@conference{541c62847bb54f2c89d82cbf4c49b6e7,

title = "Improved dynamic kernels for hitting-set",

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.",

author = "Zacharias Heinrich and Rudiger Reischuk",

note = "Publisher Copyright: {\textcopyright} Proceedings of the 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.; 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization <br/>, CTW 2019 ; Conference date: 01-07-2019 Through 03-07-2019",

year = "2019",

language = "English",

pages = "69--72",

}

TY - CONF

T1 - Improved dynamic kernels for hitting-set

AU - Heinrich, Zacharias

AU - Reischuk, Rudiger

N1 - Conference code: 159391

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85084362032

M3 - Conference Papers

SP - 69

EP - 72

T2 - 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization <br/>

Y2 - 1 July 2019 through 3 July 2019

ER -

Improved dynamic kernels for hitting-set

Abstract

Conference

DFG Research Classification Scheme

UN SDGs

Other files and links

Fingerprint

Cite this