دانلود کتاب Fundamentals of Parameterized Complexity

فهرست مطالب :

Front Matter....Pages I-XXX
Front Matter....Pages 1-1
Preliminaries....Pages 3-13
The Basic Definitions....Pages 15-21
Front Matter....Pages 23-23
Bounded Search Trees....Pages 25-47
Kernelization....Pages 49-89
More on Kernelization....Pages 91-106
Iterative Compression, and Measure and Conquer, for Minimization Problems....Pages 107-130
Further Elementary Techniques....Pages 131-141
Color Coding, Multilinear Detection, and Randomized Divide and Conquer....Pages 143-170
Optimization Problems, Approximation Schemes, and Their Relation to FPT ....Pages 171-182
Front Matter....Pages 183-183
Treewidth and Dynamic Programming....Pages 185-203
Heuristics for Treewidth....Pages 205-211
Methods via Automata and Bounded Treewidth....Pages 213-264
Courcelle’s Theorem....Pages 265-278
More on Width-Metrics: Applications and Local Treewidth....Pages 279-289
Depth-First Search and the Plehn–Voigt Theorem....Pages 291-300
Other Width Metrics....Pages 301-316
Front Matter....Pages 317-317
Well-Quasi-Orderings and the Robertson–Seymour Theorems....Pages 319-338
The Graph Minor Theorem....Pages 339-350
Applications of the Obstruction Principle and WQO s....Pages 351-372
Front Matter....Pages 373-373
Reductions....Pages 375-382
Front Matter....Pages 373-373
The Basic Class W [1] and an Analog of Cook’s Theorem....Pages 383-406
Some Other W [1] Hardness Results....Pages 407-426
The W -Hierarchy....Pages 427-459
The Monotone and Antimonotone Collapse Theorems: Monotone W [2 t +1]= W [2 t ] and Antimonotone W [2 t +2]= W [2 t +1]....Pages 461-471
Beyond W [ t ]-Hardness....Pages 473-489
Fixed Parameter Analogues of PSpace and k -Move Games....Pages 491-507
Provable Intractability: The Class XP....Pages 509-519
Another Basis for the W -Hierarchy and the Tradeoff Theorem....Pages 521-531
Front Matter....Pages 533-533
The M -Hierarchy, and XP -Optimality....Pages 535-570
Kernelization Lower Bounds....Pages 571-619
Front Matter....Pages 621-621
Parameterized Approximation....Pages 623-644
Parameterized Counting and Randomization....Pages 645-673
Front Matter....Pages 675-675
Research Horizons....Pages 677-686
Front Matter....Pages 687-687
Appendix 1: Network Flows and Matchings....Pages 689-704
Appendix 2: Menger’s Theorems....Pages 705-707
Back Matter....Pages 709-763