Optimal-size problem kernels for d-Hitting Set in linear time and space

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

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
СостояниеОпубликовано - 1 ноя 2020

Предметные области OECD FOS+WOS

  • 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ

Fingerprint

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

Цитировать