Kernels for packing and covering problems
From MaRDI portal
Recommendations
- Kernels for Packing and Covering Problems
- Kernelization of packing problems
- Kernelization algorithms for packing problems allowing overlaps
- Explicit linear kernels for packing problems
- A Problem Kernelization for Graph Packing
- Stronger bounds and faster algorithms for packing in generalized kernel systems
- An improved kernelization for \(P_{2}\)-packing
- An improved kernelization algorithm for \(r\)-set packing
- Kernelization for \(P_2\)-packing: a gerrymandering approach
- On kernels for covering and packing ILPs with small coefficients
Cites work
- (Meta) kernelization
- A 2k kernel for the cluster editing problem
- A 2k-kernelization algorithm for vertex cover based on crown decomposition
- A factor 2 approximation algorithm for the vertex cover P₃ problem
- A faster FPT algorithm for 3-path vertex cover
- A faster parameterized algorithm for set packing
- A fixed-parameter algorithm for the directed feedback vertex set problem
- A fixed-parameter algorithm for the vertex cover P₃ problem
- A kernelization algorithm for \(d\)-hitting set
- A linear kernel for co-path/cycle packing
- A measure and conquer approach for the parameterized bounded degree-one vertex deletion
- A more effective linear kernelization for cluster editing
- A multivariate framework for weighted FPT algorithms
- A parameterized perspective on packing paths of length two
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- A Problem Kernelization for Graph Packing
- A unified approximation algorithm for node-deletion problems
- An improved kernelization algorithm for \(r\)-set packing
- An improved kernelization for \(P_{2}\)-packing
- Approximating bounded degree deletion via matroid matching
- Approximation algorithm for the minimum weight connected k-subgraph cover problem
- Approximation and tidying -- a problem kernel for s-plex cluster vertex deletion
- Bidimensionality and kernels
- Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
- Conflict packing yields linear vertex-kernels for k-FAST, k-dense RTI and a related problem
- Crown reductions for the minimum weighted vertex cover problem
- Crown structures for vertex cover kernelization
- Crowns in bipartite graphs
- Efficient Parameterized Preprocessing for Cluster Editing
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fundamentals of parameterized complexity
- Gallai-type theorems and domination parameters
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Infeasibility of instance compression and succinct PCPs for NP
- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
- Kernelization for \(P_2\)-packing: a gerrymandering approach
- Kernelization of packing problems
- Kernels for feedback arc set in tournaments
- Kernels for Packing and Covering Problems
- Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths
- Looking at the stars
- Lower bounds for kernelizations and other preprocessing procedures
- Matching and weighted \(P_2\)-packing: algorithms and kernels
- Maximum-Minimum Sätze über Graphen
- Minimum \(k\)-path vertex cover
- Narrow sieves for parameterized paths and packings
- On k-dependent domination
- On a relation between \(k\)-path partition and \(k\)-path vertex cover
- On bounded-degree vertex deletion parameterized by treewidth
- On problems without polynomial kernels
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- On the parameterized complexity of vertex cover and edge cover with connectivity constraints
- On the vertex \(k\)-path cover
- Parameterized algorithms
- Parameterized and Exact Computation
- Parameterized Approximability of the Disjoint Cycle Problem
- Parameterized complexity of finding regular induced subgraphs
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterized tractability of edge-disjoint paths on directed acyclic graphs
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Randomized parameterized algorithms for P₂-packing and co-path packing problems
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Some results on graphs without long induced paths
- The complexity of dissociation set problems in graphs
- Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Vertex packings: Structural properties and algorithms
Cited in
(12)- A \(5k\)-vertex kernel for \(P_2\)-packing
- Crown structures for vertex cover kernelization
- On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
- Kernels for Packing and Covering Problems
- Stronger bounds and faster algorithms for packing in generalized kernel systems
- A Quadratic Kernel for 3-Set Packing
- Kernelization of packing problems
- Approximating the directed path partition problem
- Combining crown structures for vulnerability measures
- Combining crown structures for vulnerability measures
- An improved kernelization algorithm for \(r\)-set packing
- An improved kernelization for \(P_{2}\)-packing
This page was built for publication: Kernels for packing and covering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272393)
