Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
From MaRDI portal
Publication:6078297
DOI10.1016/J.JCSS.2023.103479arXiv2109.06042OpenAlexW3199867152MaRDI QIDQ6078297
Author name not available (Why is that?)
Publication date: 24 October 2023
Published in: (Search for Journal in Brave)
Abstract: The NP-hard Multiple Hitting Set problem is finding a minimum-cardinality set intersecting each of the sets in a given input collection a given number of times. Generalizing a well-known data reduction algorithm due to Weihe, we show a problem kernel for Multiple Hitting Set parameterized by the Dilworth number, a graph parameter introduced by Foldes and Hammer in 1978 yet seemingly so far unexplored in the context of parameterized complexity theory. Using matrix multiplication, we speed up the algorithm to quadratic sequential time and logarithmic parallel time. We experimentally evaluate our algorithms. By implementing our algorithm on GPUs, we show the feasability of realizing kernelization algorithms on SIMD (Single Instruction, Multiple Date) architectures.
Full work available at URL: https://arxiv.org/abs/2109.06042
No records found.
No records found.
This page was built for publication: Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6078297)
