The k-feature set problem is W[2]-complete

DOI10.1016/S0022-0000(03)00081-3MaRDI QIDQ1877698zbMATH OpenFDO

Authors Carlos Cotta, Pablo Moscato

Publication date 19 August 2004

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Stochastic local search for the FEATURE SET problem, with applications to microarray data
• A parameterized complexity analysis of combinatorial feature selection problems
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Consistent feature selection for pattern recognition in polynomial time
• Fixed-Parameter Tractability and Completeness I: Basic Results

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A Gentle Introduction to Memetic Algorithms
• Fixed-Parameter Tractability and Completeness I: Basic Results

Cited in

(7)

• Tight lower bounds for certain parameterized NP-hard problems
• The complexity of dependency detection and discovery in relational databases
• Stochastic local search for the FEATURE SET problem, with applications to microarray data
• A parameterized perspective on packing paths of length two
• Exploiting hidden structure in selecting dimensions that distinguish vectors
• A parameterized complexity analysis of combinatorial feature selection problems
• Separating sets of strings by finding matching patterns is almost always hard

This page was built for publication: The \(k\)-feature set problem is \(W[2]\)-complete

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