Improved dynamic kernels for hitting-set

Zacharias Heinrich; Rudiger Reischuk

Improved dynamic kernels for hitting-set

Institut für Theoretische Informatik

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.

Originalsprache	Englisch
Seiten	69-72
Seitenumfang	4
Publikationsstatus	Veröffentlicht - 2019
Veranstaltung	17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization - University of Twente, Enschede, Niederlande Dauer: 01.07.2019 → 03.07.2019 Konferenznummer: 159391

Tagung, Konferenz, Kongress

Tagung, Konferenz, Kongress	17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization
Kurztitel	CTW 2019
Land/Gebiet	Niederlande
Ort	Enschede
Zeitraum	01.07.19 → 03.07.19

DFG-Fachsystematik

409-01 Theoretische Informatik

UN SDGs

Dieser Output leistet einen Beitrag zu folgendem(n) Ziel(en) für nachhaltige Entwicklung

Andere Dateien und Links

www.scopus.com

Zitieren

@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/record/display.uri?eid=2-s2.0-85084362032&origin=inward&txGid=b9c641ab8f07dee0052ba56c7d3c3e0c

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 -