Аннотация
The known linear-time kernelizations for d-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size O(kd) for d-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for d-Hitting Set to each other and to a classical data reduction algorithm due to Weihe.
Язык оригинала | английский |
---|---|
Номер статьи | 105998 |
Число страниц | 9 |
Журнал | Information Processing Letters |
Том | 163 |
DOI | |
Состояние | Опубликовано - 1 ноя 2020 |
Предметные области OECD FOS+WOS
- 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ