Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
From MaRDI portal
Publication:372970
Recommendations
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- A kernel of order \(2k - c\) for Vertex Cover
- Improved Parameterized Upper Bounds for Vertex Cover
- Smaller parameters for vertex cover kernelization
- A kernel of order \(2k-c\log k\) for vertex cover
- Vertex cover problem parameterized above and below tight bounds
- Towards optimal kernel for connected vertex cover in planar graphs
- scientific article; zbMATH DE number 1304341
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A kernel of order \(2k - c\) for Vertex Cover
- Almost 2-SAT is fixed-parameter tractable
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Cross-composition: a new technique for kernelization lower bounds
- Crown reductions for the minimum weighted vertex cover problem
- Crown structures for vertex cover kernelization
- Graph Layout Problems Parameterized by Vertex Cover
- Graph-Theoretic Concepts in Computer Science
- Improved upper bounds for vertex cover
- Incompressibility through Colors and IDs
- Infeasibility of instance compression and succinct PCPs for NP
- Isomorphism for graphs of bounded feedback vertex set number
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Kernels for the Vertex Cover Problem on the Preferred Attachment Model
- Nondeterminism within $P^ * $
- On efficient fixed-parameter algorithms for weighted vertex cover
- On polynomial kernels for structural parameterizations of odd cycle transversal
- On problems without polynomial kernels
- On the hardness of losing width
- Parameterized complexity of vertex colouring
- Paths, flowers and vertex cover
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Reflections on multivariate algorithmics and problem parameterization
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Some consequences of non-uniform conditions on uniform classes
- Spanning trees with many leaves in cubic graphs
- The complexity ecology of parameters: An illustration using bounded max leaf number
- The complexity of König subgraph problems and above-guarantee vertex cover
- The structure and maximum number of maximum independent sets in trees
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- Two-layer planarization parameterized by feedback edge set
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Vertex cover problem parameterized above and below tight bounds
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
Cited in
(41)- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Towards a polynomial kernel for directed feedback vertex set
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- Towards a polynomial kernel for directed feedback vertex set
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Crown reductions for the minimum weighted vertex cover problem
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- A kernel of order \(2k-c\log k\) for vertex cover
- Smaller parameters for vertex cover kernelization
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- On the approximate compressibility of connected vertex cover
- Kernelization for feedback vertex set via elimination distance to a forest
- Slim tree-cut width
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- On kernelization for edge dominating set under structural parameters
- A 2k-kernelization algorithm for vertex cover based on crown decomposition
- Search-space reduction via essential vertices
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- What Is Known About Vertex Cover Kernelization?
- FPT algorithms to compute the elimination distance to bipartite graphs and more
- Structural parameterizations with modulator oblivion
- Vertex cover structural parameterization revisited
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Structural parameterizations with modulator oblivion
- Maximum minimal vertex cover parameterized by vertex cover
- Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
- Meta-kernelization using well-structured modulators
- The parameterized complexity of cycle packing: indifference is not an issue
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Parameterized complexity of computing maximum minimal blocking and hitting sets
- Kernels for the Vertex Cover Problem on the Preferred Attachment Model
- A multivariate approach for weighted FPT algorithms
- Maximum minimal vertex cover parameterized by vertex cover
- A multivariate framework for weighted FPT algorithms
This page was built for publication: Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q372970)
