On the structure of parameterized problems in NP Conference Paper

abstract

• 1994, Springer Verlag. All rights reserved. Fixed-parameter intractability of optimization problems in NP is studied based on computational models with limited nondeterminism. Strong evidence is shown that many NP optimization problems are not fixed-parameter tractable and that the fixed-parameter intractability hierarchy (the W-hierarchy) does not collapse.

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Cai, L., Chen, J., Downey, R., & Fellows, M.

complete list of authors

• Cai, L||Chen, J||Downey, R||Fellows, M

publication date

• January 1994

published in

• Lecture Notes in Artificial Intelligence  Journal

International Standard Book Number (ISBN) 13

• 9783540577850

start page

• 500

end page

• 520

volume

• 775 LNCS