Kernelization of packing problems
From MaRDI portal
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
Cites work
- (Meta) Kernelization
- \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
- A 4k^2 kernel for feedback vertex set
- A linear kernel for a planar connected dominating set
- A more effective linear kernelization for cluster editing
- A parameterized perspective on packing paths of length two
- A Problem Kernelization for Graph Packing
- An improved kernelization for \(P_{2}\)-packing
- Bidimensionality and kernels
- Combinatorial and computational aspects of graph packing and graph decomposition
- Cross-composition: a new technique for kernelization lower bounds
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 5485524 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Incompressibility through Colors and IDs
- Intersection Theorems for Systems of Sets
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Looking at the stars
- Lower bounds for kernelizations and other preprocessing procedures
- Lower bounds on kernelization
- On problems without polynomial kernels
- On the completeness of a generalized matching problem
- Parameterized and Exact Computation
- Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
- Parametrized complexity theory.
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Preprocessing of min ones problems: a dichotomy
- Properties of vertex packing and independence system polyhedra
- Reducibility among combinatorial problems
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Two edge modification problems without polynomial kernels
Cited in
(54)- Explicit linear kernels for packing problems
- Parameterized algorithms and kernels for rainbow matching
- On the approximate compressibility of connected vertex cover
- A polynomial kernel for bipartite permutation vertex deletion
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Lossy kernelization of same-size clustering
- Parameterized analysis and crossing minimization problems
- Kernels for packing and covering problems
- Optimal data reduction for graph coloring using low-degree polynomials
- A completeness theory for polynomial (Turing) kernelization
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Kernel for \(K_t\)\textsc-free Edge Deletion
- On fair covering and hitting problems
- Kernels for Packing and Covering Problems
- A shortcut to (sun)flowers: kernels in logarithmic space or linear time
- Kernelization algorithms for packing problems allowing overlaps
- Stronger bounds and faster algorithms for packing in generalized kernel systems
- Kernelization of cycle packing with relaxed disjointness constraints
- Deterministic algorithms for matching and packing problems based on representative sets
- New limits to classical and quantum instance compression
- A Problem Kernelization for Graph Packing
- A Quadratic Kernel for 3-Set Packing
- Kernel bounds for path and cycle problems
- Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems
- Parameterized complexity of induced graph matching on claw-free graphs
- Best-case and worst-case sparsifiability of Boolean CSPs
- Hans Bodlaender and the Theory of Kernelization Lower Bounds
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Exploiting c-closure in kernelization algorithms for graph problems
- An approximate kernel for connected feedback vertex set
- Parameterized Algorithms and Kernels for Rainbow Matching
- Triangle packing in (sparse) tournaments: approximation and kernelization
- Optimal data reduction for graph coloring using low-degree polynomials
- Optimal Packing Problems: From Knapsack Problem to Open Dimension Problem
- Representative sets and irrelevant vertices: new tools for kernelization
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- Parameterized certificate dispersal and its variants
- Polynomial Kernel for Interval Vertex Deletion
- Essentially tight kernels for (weakly) closed graphs
- Lossy kernelization of same-size clustering
- Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back
- When can cluster deletion with bounded weights be solved efficiently?
- Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
- Budgeted matroid maximization: a parameterized viewpoint
- Parameterized covering in semi-ladder-free hypergraphs
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Forgetfulness can make you faster: an O^*(8.097ᵏ)-time algorithm for weighted 3-set k-packing
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Polynomial kernels with reachability for weighted d-matroid intersection
- An improved kernelization algorithm for \(r\)-set packing
- Best-case and worst-case sparsifiability of Boolean CSPs
- An improved kernelization for \(P_{2}\)-packing
This page was built for publication: Kernelization of packing problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743378)
