Parameterized Complexity - Downey, Rodney G.;Fellows, M.R.
157,99 €
versandkostenfrei*

inkl. MwSt.
Versandfertig in 2-4 Wochen
Entspannt einkaufen: verlängerte Rückgabefrist1) bis zum 10.01.2022
79 °P sammeln
  • Gebundenes Buch

This monograph presents an approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking "k-slices" of the language. In doing so, the reader is introduced to new classes of algorithms which may be analysed more precisely than hereto. The authors have made the book as self-contained as possible and a lot of background material is included. As a result, computer scientists, mathematicians, and graduate students interested in the design and analysis of algorithms will find…mehr

Produktbeschreibung
This monograph presents an approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking "k-slices" of the language. In doing so, the reader is introduced to new classes of algorithms which may be analysed more precisely than hereto. The authors have made the book as self-contained as possible and a lot of background material is included. As a result, computer scientists, mathematicians, and graduate students interested in the design and analysis of algorithms will find much of interest in this book.

Contents:
- The Parametric Point of View
- Parameterized Tractability
- The Basic Definitions
- Bounded Search and Problem Kernel
- Optimization Problem, Approximation Schemes and their Relation with FPT
- The Advice View Revisited and LOGSPACE
- Automata and Bounded Treewidth
- WQO and the Robertson-Seymour Theorems
- Miscellaneous Techniques
- Parameterized Intractability
- Reductions
- An Analogue of Cook's Theorem
- Other Hardness Results
- The W-Hierarchy
- Beyond W-Hardness
- k-Move games
- Provable Intractability: the Class XP
- Structural and Other Results
- Another Basis
- Classical Complexity
- The Monotone and Antimonotone Collapses
- Parameterized Reducibilities
- Appendix
- Problem Guide and Compendium
- Research Horizons
- References
- Index
  • Produktdetails
  • Monographs in Computer Science
  • Verlag: Springer / Springer, Berlin
  • Artikelnr. des Verlages: 978-0-387-94883-6
  • Repr. d. Ausg. v. 1998
  • Seitenzahl: 556
  • Erscheinungstermin: 6. November 1998
  • Englisch
  • Abmessung: 241mm x 160mm x 34mm
  • Gewicht: 892g
  • ISBN-13: 9780387948836
  • ISBN-10: 038794883X
  • Artikelnr.: 09219254
Inhaltsangabe
1 Computers, Complexity, and Intractability from the Parametric Point of View.- 1.1 Introduction.- 1.2 The Role of Computational Complexity in Modern Science.- 1.3 The Story of Dr.O, Continued.- 1.4 Reworking the Foundations of Computational Complexity.- 1.5 A Deal with the Devil.- 1.6 How Parameters Arise in Practice.- 1.7 A Distinctive Positive Toolkit.- 1.8 O No?.- 1.9 The Barometer of Parametric Intractability.- 1.10 Structural Aspects of Parameterized Complexity.- 1.11 An Overview of Current Research Horizons.- I Parameterized Tractability.- 2 The Basic Definitions.- 2.1 Fixed-Parameter Tractability.- 2.2 The Advice View.- 3 Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel.- 3.1 The Method of Bounded Search Trees.- 3.1.1 The Basic Method.- 3.1.2 Heuristic Improvements, Shrinking the Search Tree.- 3.2 The Method of Reduction to a Problem Kernel.- 3.2.1 The Basic Method.- 3.2.2 Hereditary Properties and Leizhen Cai's Theorem.- 4 Optimization Problems,