Optimal-size problem kernels for $d$-Hitting Set in linear time and space. van Bevern, R. & Smirnov, P. V. Information Processing Letters, 2020. ![Optimal-size problem kernels for $d$-Hitting Set in linear time and space [link]](https://bibbase.org/img/filetypes/link.svg "link")
Preprint Code Poster doi abstract bibtex 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.
@article{BS20,
title = {Optimal-size problem kernels for $d$-Hitting Set in
linear time and space},
author = {René van Bevern and Pavel V. Smirnov},
year = {2020},
date = {2020-10-01},
journal = {Information Processing Letters},
volyme = {163},
pages = {105998},
doi = {10.1016/j.ipl.2020.105998},
url_Preprint = {https://arxiv.org/abs/2003.04578},
url_Code = {https://gitlab.com/PavelSmirnov/hs-lintimespace},
url_Poster = {https://figshare.com/articles/poster/Optimal-size_problem_kernels_for_d-Hitting_Set_in_linear_time_and_space/12782975},
abstract = {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.}
}
Downloads: 0
{"_id":"oYTYbSauSxhkAfaJM","bibbaseid":"vanbevern-smirnov-optimalsizeproblemkernelsfordhittingsetinlineartimeandspace-2020","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Smirnov, P. V."],"bibdata":{"bibtype":"article","type":"article","title":"Optimal-size problem kernels for $d$-Hitting Set in linear time and space","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Pavel","V."],"propositions":[],"lastnames":["Smirnov"],"suffixes":[]}],"year":"2020","date":"2020-10-01","journal":"Information Processing Letters","volyme":"163","pages":"105998","doi":"10.1016/j.ipl.2020.105998","url_preprint":"https://arxiv.org/abs/2003.04578","url_code":"https://gitlab.com/PavelSmirnov/hs-lintimespace","url_poster":"https://figshare.com/articles/poster/Optimal-size_problem_kernels_for_d-Hitting_Set_in_linear_time_and_space/12782975","abstract":"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.","bibtex":"@article{BS20,\n title =\t {Optimal-size problem kernels for $d$-Hitting Set in\n linear time and space},\n author =\t {René van Bevern and Pavel V. Smirnov},\n year =\t {2020},\n date =\t {2020-10-01},\n journal =\t {Information Processing Letters},\n volyme =\t {163},\n pages =\t {105998},\n doi =\t\t {10.1016/j.ipl.2020.105998},\n url_Preprint = {https://arxiv.org/abs/2003.04578},\n url_Code =\t {https://gitlab.com/PavelSmirnov/hs-lintimespace},\n url_Poster =\t {https://figshare.com/articles/poster/Optimal-size_problem_kernels_for_d-Hitting_Set_in_linear_time_and_space/12782975},\n abstract =\t {We improve two linear-time data reduction algorithms\n for the d-Hitting Set problem to work in linear\n space, thus obtaining the first algorithms for\n computing problem kernels of asymptotically optimal\n size O(k^d) for d-Hitting Set in linear time and\n space. We experimentally compare the two algorithms\n to a classical data reduction algorithm of Weihe and\n evaluate their combinations.}\n}\n\n\n\n","author_short":["van Bevern, R.","Smirnov, P. V."],"key":"BS20","id":"BS20","bibbaseid":"vanbevern-smirnov-optimalsizeproblemkernelsfordhittingsetinlineartimeandspace-2020","role":"author","urls":{" preprint":"https://arxiv.org/abs/2003.04578"," code":"https://gitlab.com/PavelSmirnov/hs-lintimespace"," poster":"https://figshare.com/articles/poster/Optimal-size_problem_kernels_for_d-Hitting_Set_in_linear_time_and_space/12782975"},"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}}},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:16:51.461Z","downloads":6,"keywords":[],"search_terms":["optimal","size","problem","kernels","hitting","set","linear","time","space","van bevern","smirnov"],"title":"Optimal-size problem kernels for $d$-Hitting Set in linear time and space","year":2020,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}