Lower bounds on kernelization
type: Item
instance of: scholarly article
title: Lower bounds on kernelization
zbMATH Open document ID: 1248.90078
author: Neeldhara Misra
author: Venkatesh Raman
author: Saket Saurabh
published in: Discrete Optimization
publication date: 2012-10-16T00:00:00Z
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 6094037
zbMATH Keywords: kernelization
zbMATH Keywords: lower bounds
zbMATH Keywords: composition algorithms
zbMATH Keywords: polynomial parameter transformations
zbMATH Keywords: many kernels
MaRDI profile type: Publication
full work available at URL: j.disopt.2010.10.001
OpenAlex ID: W1964699377
cites work: Polynomial-time data reduction for dominating set
cites work: Q5710169
cites work: A 4 k 2 kernel for feedback vertex set
cites work: Vertex cover: Further observations and further improvements
cites work: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
cites work: On problems without polynomial kernels
cites work: Q4947393
cites work: Parametrized complexity theory.
cites work: Q4393480
cites work: Nondeterminism within $P^ * $
cites work: Crown reductions for the minimum weighted vertex cover problem
cites work: Q4437501
cites work: Q3549693
cites work: Some consequences of non-uniform conditions on uniform classes
cites work: Lower Bounds for Kernelizations and Other Preprocessing Procedures
cites work: Incompressibility through Colors and IDs
cites work: Color-coding
cites work: Preprocessing of Min Ones Problems: A Dichotomy
cites work: Q4198056
cites work: Kernel Bounds for Disjoint Cycles and Disjoint Paths
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Q4850549
cites work: On Independent Circuits Contained in a Graph
cites work: A Cubic Kernel for Feedback Vertex Set
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
cites work: (Meta) Kernelization
cites work: Q5417644
cites work: A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
cites work: Betweenness parameterized above tight lower bound
cites work: All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables
cites work: A Generalization of Nemhauser and Trotter's Local Optimization Theorem.
cites work: A Linear Vertex Kernel for Maximum Internal Spanning Tree
cites work: Even Faster Algorithm for Set Splitting!
DOI: 10.1016/J.DISOPT.2010.10.001
Recommended article: Lower Bounds for Kernelization
Recommended article: Lower Bounds for Kernelizations and Other Preprocessing Procedures
Recommended article: Lower bounds for kernelizations and other preprocessing procedures
Recommended article: Kernelization: New Upper and Lower Bound Techniques
Recommended article: Kernelization Lower Bounds by Cross-Composition
Recommended article: A universal lower bound for the kernel estimate
Recommended article: Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
Recommended article: Fractals for Kernelization Lower Bounds
Recommended article: Lower bounds for separable approximations of the Hilbert kernel
Recommended article: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
description: scientific article; zbMATH DE number 6094037