Kernels for packing and covering problems
From MaRDI portal
Publication:2272393
DOI10.1016/j.tcs.2019.04.018zbMath1430.68127OpenAlexW2948483044WikidataQ127791242 ScholiaQ127791242MaRDI QIDQ2272393
Publication date: 10 September 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2019.04.018
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (2)
Cites Work
- Unnamed Item
- Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths
- AND-compression of NP-complete problems: streamlined proof and minor observations
- On a generalization of Nemhauser and Trotter's local optimization theorem
- Fundamentals of parameterized complexity
- Matching and weighted \(P_2\)-packing: algorithms and kernels
- A \(2k\) kernel for the cluster editing problem
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- On the parameterized complexity of vertex cover and edge cover with connectivity constraints
- Crowns in bipartite graphs
- Lower bounds for kernelizations and other preprocessing procedures
- Infeasibility of instance compression and succinct PCPs for NP
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- Kernels for feedback arc set in tournaments
- On bounded-degree vertex deletion parameterized by treewidth
- An improved kernelization algorithm for \(r\)-set packing
- Kernelization for \(P_2\)-packing: a gerrymandering approach
- Looking at the stars
- A parameterized perspective on packing paths of length two
- A faster FPT algorithm for 3-path vertex cover
- A kernelization algorithm for \(d\)-hitting set
- An improved kernelization for \(P_{2}\)-packing
- A more effective linear kernelization for cluster editing
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Parameterized complexity of finding regular induced subgraphs
- Some results on graphs without long induced paths
- On problems without polynomial kernels
- A faster parameterized algorithm for set packing
- A unified approximation algorithm for node-deletion problems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Gallai-type theorems and domination parameters
- On \(k\)-dependent domination
- A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- Parameterized complexity of finding subgraphs with hereditary properties.
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- On a relation between \(k\)-path partition and \(k\)-path vertex cover
- Minimum \(k\)-path vertex cover
- The complexity of dissociation set problems in graphs
- Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
- Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
- Narrow sieves for parameterized paths and packings
- A multivariate framework for weighted FPT algorithms
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- On the vertex \(k\)-path cover
- Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
- Crown structures for vertex cover kernelization
- Crown reductions for the minimum weighted vertex cover problem
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps
- Kernels for Packing and Covering Problems
- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
- Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem
- (Meta) Kernelization
- A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
- Maximum-Minimum Sätze über Graphen
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- A Linear Kernel for Co-Path/Cycle Packing
- A Problem Kernelization for Graph Packing
- Vertex packings: Structural properties and algorithms
- Approximating Bounded Degree Deletion via Matroid Matching
- Parameterized and Exact Computation
- Bidimensionality and Geometric Graphs
- Parameterized Approximability of the Disjoint Cycle Problem
- Efficient Parameterized Preprocessing for Cluster Editing
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Graph-Theoretic Concepts in Computer Science
- Algorithms - ESA 2003
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Kernels for packing and covering problems
