Lower bounds on kernelization
From MaRDI portal
Recommendations
- Lower bounds for kernelization
- Lower bounds for kernelizations and other preprocessing procedures
- Lower bounds for kernelizations and other preprocessing procedures
- Kernelization: new upper and lower bound techniques
- Kernelization Lower Bounds by Cross-Composition
- A universal lower bound for the kernel estimate
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Fractals for kernelization lower bounds
- Lower bounds for separable approximations of the Hilbert kernel
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
Cites work
- Title not available (Why is no real title available?)
- scientific article; zbMATH DE number 5485524 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 2011849 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- scientific article; zbMATH DE number 6297727 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- (Meta) Kernelization
- A Cubic Kernel for Feedback Vertex Set
- A generalization of Nemhauser and Trotter's local optimization theorem
- A linear vertex kernel for Maximum Internal Spanning Tree
- A probabilistic approach to problems parameterized above or below tight bounds
- All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
- Betweenness parameterized above tight lower bound
- Color-coding
- Crown reductions for the minimum weighted vertex cover problem
- Even faster algorithm for set splitting!
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Graph-Theoretic Concepts in Computer Science
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Lower bounds for kernelizations and other preprocessing procedures
- Nondeterminism within $P^ * $
- On Independent Circuits Contained in a Graph
- On problems without polynomial kernels
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Parametrized complexity theory.
- Polynomial-time data reduction for dominating set
- Preprocessing of min ones problems: a dichotomy
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Some consequences of non-uniform conditions on uniform classes
- Vertex cover: Further observations and further improvements
- \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
Cited in
(38)- Lower bounds for kernelizations and other preprocessing procedures
- Studies in Computational Aspects of Voting
- Lower bounds for kernelizations and other preprocessing procedures
- A Retrospective on (Meta) Kernelization
- Kernelization Lower Bounds by Cross-Composition
- Lower bounds for separable approximations of the Hilbert kernel
- Smaller kernels for several FPT problems based on simple observations
- What's next? Future directions in parameterized complexity
- An improved kernel for max-bisection above tight lower bound
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- Parameterized complexity of machine scheduling: 15 open problems
- Streaming kernelization
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Kernelization -- preprocessing with a guarantee
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Recent developments in kernelization: a survey
- Towards optimal kernel for edge-disjoint triangle packing
- What Is Known About Vertex Cover Kernelization?
- STACS 2005
- Meta-kernelization with structural parameters
- Diminishable parameterized problems and strict polynomial kernelization
- Diminishable parameterized problems and strict polynomial kernelization
- Kernelization lower bounds for finding constant-size subgraphs
- Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods
- Computing kernels in parallel: lower and upper bounds
- Algorithmic Learning Theory
- Kernels: Annotated, Proper and Induced
- Kernelization of packing problems
- Lower bounds for kernelization
- Parameterized complexity and kernel bounds for hard planning problems
- On some FPT problems without polynomial Turing compressions
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Lossy kernelization
- Bidimensionality and kernels
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- Confluence in data reduction: bridging graph transformation and kernelization
- A hierarchy of polynomial kernels
This page was built for publication: Lower bounds on kernelization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456702)
