An improved kernelization algorithm for \(r\)-set packing
From MaRDI portal
Publication:765496
DOI10.1016/j.ipl.2010.04.020zbMath1233.05082OpenAlexW2079277986MaRDI QIDQ765496
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
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