An improved kernelization algorithm for \(r\)-set packing

DOI10.1016/j.ipl.2010.04.020zbMath1233.05082OpenAlexW2079277986MaRDI QIDQ765496

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

zbMATH Keywords

set packinggraph algorithmsfixed-parameter algorithmskernelizationcrown decomposition

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial aspects of packing and covering (05B40)

Related Items

Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition ⋮ Packing arc-disjoint cycles in tournaments ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs ⋮ Parameterized complexity of path set packing ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ Arbitrary Overlap Constraints in Graph Packing Problems ⋮ Kernels for packing and covering problems ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ Parameterized Algorithms and Kernels for Rainbow Matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A faster parameterized algorithm for set packing
• Crown structures for vertex cover kernelization
• Vertex Cover: Further Observations and Further Improvements
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• On Problems without Polynomial Kernels (Extended Abstract)
• Faster Algebraic Algorithms for Path and Packing Problems
• Kernelization Algorithms for d-Hitting Set Problems
• An efficient parameterized algorithm for m-set packing
• Parameterized Algorithms for Weighted Matching and Packing Problems
• Algorithms – ESA 2004
• Graph-Theoretic Concepts in Computer Science