A faster parameterized algorithm for set packing

DOI10.1016/J.IPL.2004.12.005MaRDI QIDQ1041711zbMATH OpenOpenAlexFDO

Authors Ioannis Koutis

Publication date 4 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2004.12.005

zbMATH Keywords

analysis of algorithmsparameterized computationset packing

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• An efficient parameterized algorithm for m-set packing
• A fixed-parameter-tractable algorithm for set packing
• A fast approximation algorithm for solving the complete set packing problem
• On the parameterized complexity of compact set packing
• Parameterized approximation algorithms for packing problems
• Algorithms – ESA 2004
• Faster fixed-parameter tractable algorithms for matching and packing problems
• On the complexity of approximating \(k\)-set packing
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• Parameterized complexity of path set packing

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• An efficient parameterized algorithm for m-set packing
• Color-coding

Cited in

(19)

• An efficient parameterized algorithm for m-set packing
• Parametric packing of selfish items and the subset sum algorithm
• The \(k\)-distinct language: parameterized automata constructions
• Upper bounds on the average number of iterations for some algorithms of solving the set packing problem
• Parameterized approximation algorithms for packing problems
• Maximum disjoint paths on edge-colored graphs: approximability and tractability
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• A fixed-parameter-tractable algorithm for set packing
• Improved deterministic algorithms for weighted matching and packing problems
• An improved kernelization algorithm for \(r\)-set packing
• Narrow sieves for parameterized paths and packings
• Faster fixed-parameter tractable algorithms for matching and packing problems
• On counting 3-D matchings of size \(k\)
• Parameterized complexity of path set packing
• Mixing Color Coding-Related Techniques
• Deterministic algorithms for matching and packing problems based on representative sets
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Kernels for packing and covering problems
• An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem

This page was built for publication: A faster parameterized algorithm for set packing

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