Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU | Sciact - Система учета научной деятельности ИМ СО РАН

Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU Научная публикация

Журнал

Journal of Computer and System Sciences
ISSN: 1090-2724

Вых. Данные

Год: 2024, Том: 139, Номер статьи : 103479, Страниц : 18 DOI: 10.1016/j.jcss.2023.103479

Ключевые слова

NP-hard problem, Data reduction, Problem kernelization, Parallel algorithm, Computational experiment, GPU, Parameterized complexity

Авторы

van Bevern Rene ¹ , Kirilin Artem M. ² , Skachkov Daniel A. ³ , Smirnov Pavel V. ⁴ , Tsidulko Oxana Yu. ⁵

Организации

1	Huawei Technologies Co., Ltd
2	Siberian Federal University
3	Moscow Institute of Physics and Technology
4	Recraft
5	Sobolev Institute of Mathematics

Информация о финансировании (2)

1	Математический центр в Академгородке	075-15-2019-1675
2	Российский фонд фундаментальных исследований	18-501-12031 NNIO_a

The NP-hard Multiple Hitting Set problem is the problem of 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 feasibility of realizing kernelization algorithms on SIMD (Single Instruction, Multiple Data) architectures.

van Bevern R. , Kirilin A.M. , Skachkov D.A. , Smirnov P.V. , Tsidulko O.Y.
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
Journal of Computer and System Sciences. 2024. V.139. 103479 :1-18. DOI: 10.1016/j.jcss.2023.103479 WOS Scopus РИНЦ OpenAlex

Поступила в редакцию:	17 сент. 2021 г.
Принята к публикации:	23 авг. 2023 г.
Опубликована online:	12 сент. 2023 г.
Опубликована в печати:	15 февр. 2024 г.

Web of science:	WOS:001086672700001
Scopus:	2-s2.0-85172014632
РИНЦ:	64856247
OpenAlex:	W3199867152

Пока нет цитирований