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

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

Cited in

(22)

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

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)