Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
From MaRDI portal
Publication:2093577
Recommendations
- A new framework for kernelization lower bounds: the case of maximum minimal vertex cover
- Maximum minimal vertex cover parameterized by vertex cover
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
Cites work
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- scientific article; zbMATH DE number 7651162 (Why is no real title available?)
- (Meta) kernelization
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Approximating minimum independent dominating sets in wireless networks
- Approximation algorithms inspired by kernelization methods
- Approximation in (Poly-) Logarithmic Space
- Easy problems for tree-decomposable graphs
- Extension of Vertex Cover and Independent Set in some classes of graphs
- Fundamentals of parameterized complexity
- Independent dominating sets in triangle-free graphs
- Independent domination in finitely defined classes of graphs
- Independent domination in graphs: A survey and recent results
- Independent domination in triangle-free graphs
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- Kernel(s) for problems with no kernel
- Kernelization Lower Bounds by Cross-Composition
- Kernelization of packing problems
- Kernelization. Theory of parameterized preprocessing
- Linear time solvable optimization problems on graphs of bounded clique-width
- Lossy kernelization
- Maximum minimal vertex cover parameterized by vertex cover
- On domination and independent domination numbers of a graph
- On graphs with equal domination and independent domination numbers
- On problems without polynomial kernels
- On the max min vertex cover problem
- Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Ramsey-type theorems
- Ramsey-type theorems with forbidden subgraphs
- Safe approximation and its relation to kernelization
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Sparsification and subexponential approximation
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- The Erdős-Hajnal conjecture for bull-free graphs
- The Erdős-Hajnal conjecture. A survey
- The design of approximation algorithms
- The four-colour theorem
- The many facets of upper domination
- The vectorization of ITPACK 2C
- Time-approximation trade-offs for inapproximable problems
- Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(4)
This page was built for publication: Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2093577)
