An improved kernelization algorithm for r-set packing
From MaRDI portal
Publication:765496
DOI10.1016/J.IPL.2010.04.020zbMATH Open1233.05082OpenAlexW2079277986MaRDI QIDQ765496FDOQ765496
Authors: Faisal N. Abu-Khzam 
Publication date: 19 March 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2010.04.020
Recommendations
- An improved kernelization for \(P_{2}\)-packing
- Kernelization of packing problems
- Kernelization algorithms for packing problems allowing overlaps
- Stronger bounds and faster algorithms for packing in generalized kernel systems
- Kernels for Packing and Covering Problems
- Approximating the \(k\)-set packing problem by local improvements
- Kernels for packing and covering problems
- An efficient parameterized algorithm for m-set packing
- On the complexity of approximating \(k\)-set packing
- A Problem Kernelization for Graph Packing
Graph algorithms (graph-theoretic aspects) (05C85) Hypergraphs (05C65) Combinatorial aspects of packing and covering (05B40)
Cites Work
- Title not available (Why is that?)
- A faster parameterized algorithm for set packing
- Faster Algebraic Algorithms for Path and Packing Problems
- An efficient parameterized algorithm for m-set packing
- Title not available (Why is that?)
- Crown structures for vertex cover kernelization
- Vertex cover: Further observations and further improvements
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Graph-Theoretic Concepts in Computer Science
- Kernelization Algorithms for d-Hitting Set Problems
- A set packing approach for scheduling elective surgical procedures
- On Problems without Polynomial Kernels (Extended Abstract)
- Parameterized Algorithms for Weighted Matching and Packing Problems
- Algorithms – ESA 2004
Cited In (18)
- Kernelization Algorithms for Packing Problems Allowing Overlaps
- Parameterized algorithms and kernels for rainbow matching
- What's next? Future directions in parameterized complexity
- Parameterized Algorithms and Kernels for Rainbow Matching
- Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs
- A Quadratic Kernel for 3-Set Packing
- Arbitrary Overlap Constraints in Graph Packing Problems
- Packing Arc-Disjoint Cycles in Tournaments
- A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition
- Stronger bounds and faster algorithms for packing in generalized kernel systems
- An improved kernelization for \(P_{2}\)-packing
- Parameterized complexity of path set packing
- Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs
- Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
- Packing arc-disjoint cycles in tournaments
- Kernels for packing and covering problems
- Kernels for Packing and Covering Problems
- Packing arc-disjoint cycles in oriented graphs
This page was built for publication: An improved kernelization algorithm for \(r\)-set packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765496)
