Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
type: Item
instance of: scholarly article
title: Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
zbMATH Open document ID: 1462.68085
author: René van Bevern
author: Pavel V. Smirnov
published in: Information Processing Letters
publication date: 2020-10-07T00:00:00Z
full work available at URL: https://arxiv.org/abs/2003.04578
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7256105
zbMATH Keywords: combinatorial problems
zbMATH Keywords: NP-hard problem
zbMATH Keywords: data reduction
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization
MaRDI profile type: Publication
OpenAlex ID: W3010681100
arXiv ID: 2003.04578
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: Experiments on data reduction for optimal domination in networks
cites work: Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
cites work: Towards optimal and expressive kernelization for \(d\)-hitting set
cites work: Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
cites work: Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
cites work: Strong inconsistency
cites work: Introduction to algorithms
cites work: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Streaming Kernelization
cites work: A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
cites work: Parametrized complexity theory.
cites work: Kernelization
cites work: Exploiting hidden structure in selecting dimensions that distinguish vectors
cites work: Fixed-parameter algorithms for cluster vertex deletion
cites work: Reducibility among Combinatorial Problems
cites work: Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
cites work: The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment
cites work: A general method to speed up fixed-parameter-tractable algorithms
cites work: An efficient fixed-parameter algorithm for 3-hitting set
cites work: A theory of diagnosis from first principles
cites work: Exploiting a hypergraph model for finding Golomb rulers
DOI: 10.1016/J.IPL.2020.105998
description: scientific article