A Quadratic Kernel for 3-Set Packing

DOI10.1007/978-3-642-02017-9_11MaRDI QIDQ3630192zbMATH OpenOpenAlexFDO

Authors Faisal N. Abu-Khzam

Publication date 3 June 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02017-9_11

zbMATH Keywords

fixed-parameter algorithmskernelizationset packingcrown decomposition

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Nonnumerical algorithms (68W05) Combinatorial aspects of packing and covering (05B40)

Recommendations

• Subquadratic kernels for implicit 3-hitting set and 3-set packing problems
• Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems
• An improved kernelization algorithm for \(r\)-set packing
• Kernelization of packing problems
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• An improved algorithm for weighted 3-set packing
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• Kernels for packing and covering problems
• Kernels for Packing and Covering Problems
• An improved kernelization for \(P_{2}\)-packing

Cited in

(8)

• A kernelization algorithm for \(d\)-hitting set
• A (3+)k-vertex kernel for edge-disjoint triangle packing
• Subquadratic kernels for implicit 3-hitting set and 3-set packing problems
• Confronting intractability via parameters
• An improved kernel for planar vertex-disjoint triangle packing
• Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems
• Kernelization of packing problems
• Triangle packing in (sparse) tournaments: approximation and kernelization

This page was built for publication: A Quadratic Kernel for 3-Set Packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3630192)