Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
From MaRDI portal
Publication:372970
DOI10.1007/S00224-012-9393-4zbMATH Open1286.68196DBLPjournals/mst/JansenB13OpenAlexW3122973673WikidataQ59567529 ScholiaQ59567529MaRDI QIDQ372970FDOQ372970
Authors: Bart M. P. Jansen, Hans L. Bodlaender 
Publication date: 21 October 2013
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-012-9393-4
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
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Incompressibility through Colors and IDs
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Title not available (Why is that?)
- The complexity of König subgraph problems and above-guarantee vertex cover
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- Infeasibility of instance compression and succinct PCPs for NP
- Improved upper bounds for vertex cover
- Parameterized complexity of vertex colouring
- Nondeterminism within $P^ * $
- Some consequences of non-uniform conditions on uniform classes
- Isomorphism for graphs of bounded feedback vertex set number
- Graph Layout Problems Parameterized by Vertex Cover
- On efficient fixed-parameter algorithms for weighted vertex cover
- Cross-composition: a new technique for kernelization lower bounds
- Reflections on multivariate algorithmics and problem parameterization
- Crown structures for vertex cover kernelization
- Crown reductions for the minimum weighted vertex cover problem
- Vertex cover: Further observations and further improvements
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Graph-Theoretic Concepts in Computer Science
- On polynomial kernels for structural parameterizations of odd cycle transversal
- On the hardness of losing width
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Spanning trees with many leaves in cubic graphs
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Paths, flowers and vertex cover
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Two-layer planarization parameterized by feedback edge set
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- The structure and maximum number of maximum independent sets in trees
- Kernels for the Vertex Cover Problem on the Preferred Attachment Model
- A kernel of order \(2k - c\) for Vertex Cover
- Vertex cover problem parameterized above and below tight bounds
- The complexity ecology of parameters: An illustration using bounded max leaf number
Cited In (41)
- Title not available (Why is that?)
- Towards a polynomial kernel for directed feedback vertex set
- Towards a polynomial kernel for directed feedback vertex set
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- 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
- Kernelization for feedback vertex set via elimination distance to a forest
- On the approximate compressibility of connected vertex cover
- 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
- Search-space reduction via essential vertices
- A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition
- 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
- What Is Known About Vertex Cover Kernelization?
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- FPT algorithms to compute the elimination distance to bipartite graphs and more
- Vertex cover structural parameterization revisited
- Structural parameterizations with modulator oblivion
- Structural parameterizations with modulator oblivion
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Maximum minimal vertex cover parameterized by vertex cover
- Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
- The parameterized complexity of cycle packing: indifference is not an issue
- Meta-kernelization using well-structured modulators
- 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
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Polynomial kernels for hitting forbidden minors under structural parameterizations
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)
