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

DOI10.1016/S0022-0000(03)00081-3zbMATH Open1114.68426MaRDI QIDQ1877698FDOQ1877698

Authors: Carlos Cotta, Pablo Moscato 

Publication date: 19 August 2004

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

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

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)

Cites Work

• Title not available (Why is that?)
• Fixed-Parameter Tractability and Completeness I: Basic Results
• A Gentle Introduction to Memetic Algorithms

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)