ON THE STRUCTURE OF PARAMETERIZED PROBLEMS IN NP Academic Article

abstract

• 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. 1995 Academic Press, Inc.

authors

• Chen, Jianer

published proceedings

• INFORMATION AND COMPUTATION

author list (cited authors)

• CAI, L. M., CHEN, J., DOWNEY, R., & FELLOWS, M.

citation count

• 24

complete list of authors

• CAI, LM||CHEN, J||DOWNEY, R||FELLOWS, M

publication date

• November 1995

publisher

• Elsevier  Publisher

published in

• Information and Computation  Journal

Digital Object Identifier (DOI)

• 10.1006/inco.1995.1156

start page

• 38

end page

• 49

volume

• 123

issue

• 1

URL

• http%3A%2F%2Fdx.doi.org%2F10.1006%2Finco.1995.1156