ON THE STRUCTURE OF PARAMETERIZED PROBLEMS IN NP

Authors
CAI LM CHEN J DOWNEY R FELLOWS M
Citation
Lm. Cai et al., ON THE STRUCTURE OF PARAMETERIZED PROBLEMS IN NP, Information and computation, 123(1), 1995, pp. 38-49
Citations number
27
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
123
Issue
1
Year of publication
1995
Pages
38 - 49
Database
ISI
SICI code
0890-5401(1995)123:1<38:OTSOPP>2.0.ZU;2-I
Abstract
Fixed-parameter intractability of optimization problems in NP is studi ed based on computational models with limited nondeterminism. Strong e vidence is shown that many NP optimization problems are not fixed-para meter tractable and that the fixed-parameter intractability hierarchy (the W-hierarchy) does not collapse. (C) 1995 Academic Press. Inc.