This monograph presents an approach to complexity theory which offers a meansof analysing algorithms in terms of their tractability. The authors considerthe pro... » 

This monograph presents an approach to complexity theory which offers a meansof analysing algorithms in terms of their tractability. The authors considerthe problem in terms of parameterized languages and taking quotkslicesquotof the language. In doing so the reader is introduced to new classes ofalgorithms which may be analysed more precisely than hereto. The authors havemade the book as selfcontained as possible and a lot of background material isincluded. As a result computer scientists mathematicians and graduatestudents interested in the design and analysis of algorithms will find much ofinterest in this book. TOCThe Parametric Point of View. ParameterizedTractability. The Basic Definitions. Bounded Search and Problem Kernel.Optimization Problem Approximation Schemes and their Relation with FPT. TheAdvice View Revisited and LOGSPACE. Automata and Bounded Treewidth. WQO and theRobertsonSeymour Theorems. Miscellaneous Techniques. ParameterizedIntractability. Reductions. An Analogue of Cooks Theorem. Other HardnessResults. The WHierarchy. Beyond WHardness. kMove games. ProvableIntractability the Class XP. Structural and Other Results. Another Basis.Classical Complexity. The Monotone and Antimonotone Collapses. ParameterizedReducibilities. Appendix. Problem Guide and Compendium. Research Horizons.References. Index «