1 Цитирования (Scopus)

Аннотация

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
СостояниеПринято в печать - 4 июл 2020

Fingerprint Подробные сведения о темах исследования «Optimal-size problem kernels for d-Hitting Set in linear time and space». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать