Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
type: Item
instance of: scholarly article
title: Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
zbMATH Open document ID: 1236.68097
author: Stefan Kratsch
published in: Algorithmica
publication date: 2012-04-26T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6028476
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: kernelization
zbMATH Keywords: parameterized complexity
MaRDI profile type: Publication
full work available at URL: s00453-011-9559-5
OpenAlex ID: W2107285530
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: Proof verification and the hardness of approximation problems
cites work: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
cites work: Kernelization: New Upper and Lower Bound Techniques
cites work: Kernel Bounds for Disjoint Cycles and Disjoint Paths
cites work: (Meta) Kernelization
cites work: On problems without polynomial kernels
cites work: On fixed-parameter tractability and approximability of NP optimization problems
cites work: Fixed-parameter approximation: conceptual framework and approximability results
cites work: Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10--11, 2009. Revised selected papers
cites work: Vertex cover: Further observations and further improvements
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: Incompressibility through Colors and IDs
cites work: Q4393480
cites work: Intersection Theorems for Systems of Sets
cites work: Q4058132
cites work: Improved Approximation Algorithms for Minimum Weight Vertex Separators
cites work: Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
cites work: Bidimensionality and Geometric Graphs
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Q4198056
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: On Syntactic versus Computational Views of Approximability
cites work: Logical definability of NP optimization problems
cites work: Approximation properties of NP minimization classes
cites work: Two Edge Modification Problems without Polynomial Kernels
cites work: Preprocessing of Min Ones Problems: A Dichotomy
cites work: Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems
cites work: Parameterizing MAX SNP Problems Above Guaranteed Values
cites work: Parameterizing above or below guaranteed values
cites work: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
cites work: A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
cites work: Q5710169
cites work: Q3221403
cites work: Optimization, approximation, and complexity classes
cites work: Depth-first search and the vertex cover problem
cites work: Q4290987
DOI: 10.1007/S00453-011-9559-5
description: scientific article