Standard

Optimal-size problem kernels for d-Hitting Set in linear time and space. / van Bevern, René; Smirnov, Pavel V.

In: Information Processing Letters, Vol. 163, 105998, 01.11.2020.

Research output: Contribution to journal › Article › peer-review

Harvard

van Bevern, R & Smirnov, PV 2020, 'Optimal-size problem kernels for d-Hitting Set in linear time and space', Information Processing Letters, vol. 163, 105998. https://doi.org/10.1016/j.ipl.2020.105998

APA

van Bevern, R., & Smirnov, P. V. (2020). Optimal-size problem kernels for d-Hitting Set in linear time and space. Information Processing Letters, 163, [105998]. https://doi.org/10.1016/j.ipl.2020.105998

Vancouver

van Bevern R, Smirnov PV. Optimal-size problem kernels for d-Hitting Set in linear time and space. Information Processing Letters. 2020 Nov 1;163:105998. doi: 10.1016/j.ipl.2020.105998

Author

van Bevern, René ; Smirnov, Pavel V. / Optimal-size problem kernels for d-Hitting Set in linear time and space. In: Information Processing Letters. 2020 ; Vol. 163.

BibTeX

@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.}",
note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",
year = "2020",
month = nov,
day = "1",
doi = "10.1016/j.ipl.2020.105998",
language = "English",
volume = "163",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",

}

RIS

TY - JOUR

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

AU - van Bevern, René

AU - Smirnov, Pavel V.

N1 - Publisher Copyright: © 2020 Elsevier B.V.

PY - 2020/11/1

Y1 - 2020/11/1

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 -

ID: 24765520