Authors
Liming Cai, Jianer Chen, Rodney G Downey, Michael R Fellows
Publication date
1997/3/6
Journal
Annals of pure and applied logic
Volume
84
Issue
1
Pages
119-138
Publisher
North-Holland
Description
Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved (uniformly with respect to the parameter) in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it is shown that the class FPT of tractable parameterized problems (the parameterized analog of P) has interesting and natural internal structure.
Total citations
Scholar articles
L Cai, J Chen, RG Downey, MR Fellows - Annals of pure and applied logic, 1997