## RenĂ© van Bevern and Pavel V. Smirnov.
Optimal-size problem kernels for *d*-hitting set in linear time and
space.
*Information Processing Letters*, page 105998, 2020.

We improve two linear-time data reduction algorithms
for the d-Hitting Set problem to work in linear
space, thus obtaining the first algorithms for
computing problem kernels of asymptotically optimal
size O(k^d) for d-Hitting Set in linear time and
space. We experimentally compare the two algorithms
to a classical data reduction algorithm of Weihe and
evaluate their combinations.

[ bib |
DOI |
source code |
http ]
Back

*This file was generated by
bibtex2html 1.99.*