Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
From MaRDI portal
Publication:2203595
DOI10.1016/J.IPL.2020.105998zbMATH Open1462.68085arXiv2003.04578OpenAlexW3010681100MaRDI QIDQ2203595
Author name not available (Why is that?)
Publication date: 7 October 2020
Published in: (Search for Journal in Brave)
Abstract: The known linear-time kernelizations for -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 for -Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for -Hitting Set to each other and to a classical data reduction algorithm due to Weihe.
Full work available at URL: https://arxiv.org/abs/2003.04578
No records found.
No records found.
This page was built for publication: Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2203595)
