A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
From MaRDI portal
Publication:3177162
DOI10.1137/16M1104585zbMath1396.68059OpenAlexW2545198300WikidataQ129456941 ScholiaQ129456941MaRDI QIDQ3177162
Publication date: 27 July 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1104585
Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (4)
Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ On the approximate compressibility of connected vertex cover
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Fundamentals of parameterized complexity
- Kernel bounds for disjoint cycles and disjoint paths
- The complexity of König subgraph problems and above-guarantee vertex cover
- Improved upper bounds for vertex cover
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- A parameterized view on matroid optimization problems
- Matching theory
- Which problems have strongly exponential complexity?
- On the hardness of losing width
- Applications of Menger's graph theorem
- Vertex Cover: Further Observations and Further Improvements
- On Multiway Cut Parameterized above Lower Bounds
- Paths, Flowers and Vertex Cover
- Vertex packings: Structural properties and algorithms
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
- Faster Parameterized Algorithms Using Linear Programming
- Integer Programming: Methods, Uses, Computations
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
This page was built for publication: A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
