Optimal-size problem kernels for d-Hitting Set in linear time and space

René van Bevern; Pavel V. Smirnov

doi:10.1016/j.ipl.2020.105998

Optimal-size problem kernels for d-Hitting Set in linear time and space

René van Bevern, Pavel V. Smirnov

Результат исследования: Научные публикации в периодических изданиях › статья

1 Цитирования (Scopus)

Аннотация

The known linear-time kernelizations for d-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size O(k^d) for d-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for d-Hitting Set to each other and to a classical data reduction algorithm due to Weihe.

Язык оригинала	английский
Номер статьи	105998
Число страниц	9
Журнал	Information Processing Letters
Том	163
DOI	https://doi.org/10.1016/j.ipl.2020.105998
Состояние	Принято в печать - 4 июл 2020

Доступ к документу

10.1016/j.ipl.2020.105998

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «Optimal-size problem kernels for d-Hitting Set in linear time and space». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@article{0f43df8947d84d419ec252fe40388ad9,

title = "Optimal-size problem kernels for d-Hitting Set in linear time and space",

abstract = "The known linear-time kernelizations for d-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size O(kd) for d-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for d-Hitting Set to each other and to a classical data reduction algorithm due to Weihe.",

keywords = "Combinatorial problems, Data reduction, Kernelization, NP-hard problem, Parameterized complexity",

author = "{van Bevern}, Ren{\'e} and Smirnov, {Pavel V.}",

year = "2020",

month = jul,

day = "4",

doi = "10.1016/j.ipl.2020.105998",

language = "English",

volume = "163",

journal = "Information Processing Letters",

issn = "0020-0190",

}

TY - JOUR

T1 - Optimal-size problem kernels for d-Hitting Set in linear time and space

AU - van Bevern, René

AU - Smirnov, Pavel V.

PY - 2020/7/4

Y1 - 2020/7/4

N2 - The known linear-time kernelizations for d-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size O(kd) for d-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for d-Hitting Set to each other and to a classical data reduction algorithm due to Weihe.

AB - The known linear-time kernelizations for d-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size O(kd) for d-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for d-Hitting Set to each other and to a classical data reduction algorithm due to Weihe.

KW - Combinatorial problems

KW - Data reduction

KW - Kernelization

KW - NP-hard problem

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=85087713620&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2020.105998

DO - 10.1016/j.ipl.2020.105998

M3 - Article

AN - SCOPUS:85087713620

VL - 163

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

M1 - 105998

ER -