Preprocessing of Min Ones Problems: A Dichotomy
From MaRDI portal
Publication:3587416
DOI10.1007/978-3-642-14165-2_55zbMath1288.68132arXiv0910.4518OpenAlexW2118728198MaRDI QIDQ3587416
Magnus Wahlström, Stefan Kratsch
Publication date: 7 September 2010
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0910.4518
Related Items (13)
Two edge modification problems without polynomial kernels ⋮ Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ Unnamed Item ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Lower bounds on kernelization ⋮ Constraint Satisfaction Parameterized by Solution Size ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A completeness theory for polynomial (Turing) kernelization
This page was built for publication: Preprocessing of Min Ones Problems: A Dichotomy
