|
Abstract : |
This document includes a list of computational problems that have been studied within the framework of parameterized complexity [81]. It is mainly based on ?A Compendium of Parameterized Complexity Results?, version 2.0 (May 22, 1996), by Michael T. Hallett and H. Todd Wareham, and on Downey and Fellows ? book [81]. It includes, however, several new results that have been published in the last few years. Every computational problem in this document has one or more parameterized versions. Currently there are 312 computational problems listed in alphabetical order. For each of them we report the known parameterized versions (for a grand total of 376), the corresponding parameterized complexity results, and the references to the relevant articles in the bibliography. This document does not pretend, of course, to be complete; for instance, it does not consider computational problems that are not decision problems. Moreover, this document likely includes errors and omissions. If you have corrections, suggestions, new or missing results, please send them to, |
