RenĂ© van Bevern and Pavel V. Smirnov. Optimal-size problem kernels for d-hitting set in linear time and space. Information Processing Letters, to appear.

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.