Atjaunināt sīkdatņu piekrišanu

Fundamentals of Parameterized Complexity Softcover reprint of the original 1st ed. 2013 [Mīkstie vāki]

2.50/5 (2 ratings by Goodreads)
,
  • Formāts: Paperback / softback, 763 pages, height x width: 235x155 mm, weight: 1199 g, 83 Illustrations, black and white; XXX, 763 p. 83 illus., 1 Paperback / softback
  • Sērija : Texts in Computer Science
  • Izdošanas datums: 27-Aug-2016
  • Izdevniecība: Springer London Ltd
  • ISBN-10: 1447171640
  • ISBN-13: 9781447171645
Citas grāmatas par šo tēmu:
  • Mīkstie vāki
  • Cena: 82,61 €*
  • * ši ir gala cena, t.i., netiek piemērotas nekādas papildus atlaides
  • Standarta cena: 97,19 €
  • Ietaupiet 15%
  • Grāmatu piegādes laiks ir 3-4 nedēļas, ja grāmata ir uz vietas izdevniecības noliktavā. Ja izdevējam nepieciešams publicēt jaunu tirāžu, grāmatas piegāde var aizkavēties.
  • Daudzums:
  • Ielikt grozā
  • Piegādes laiks - 4-6 nedēļas
  • Pievienot vēlmju sarakstam
Fundamentals of Parameterized Complexity Softcover reprint of the original 1st ed. 2013Palielināt
  • Formāts: Paperback / softback, 763 pages, height x width: 235x155 mm, weight: 1199 g, 83 Illustrations, black and white; XXX, 763 p. 83 illus., 1 Paperback / softback
  • Sērija : Texts in Computer Science
  • Izdošanas datums: 27-Aug-2016
  • Izdevniecība: Springer London Ltd
  • ISBN-10: 1447171640
  • ISBN-13: 9781447171645
Citas grāmatas par šo tēmu:
Permanent link: https://www.kriso.lv/db/9781447171645.html
Keywords:

This text covers the state of the art in multivariate algorithmics and complexity, a vital field with countless applications in modern computing. It describes the latest methods of proving parameterized tractability, including powerful lower-bound techniques.



This comprehensive and self-contained textbook presents an accessible overview of the state of the art of multivariate algorithmics and complexity. Increasingly, multivariate algorithmics is having significant practical impact in many application domains, with even more developments on the horizon. The text describes how the multivariate framework allows an extended dialog with a problem, enabling the reader who masters the complexity issues under discussion to use the positive and negative toolkits in their own research. Features: describes many of the standard algorithmic techniques available for establishing parametric tractability; reviews the classical hardness classes; explores the various limitations and relaxations of the methods; showcases the powerful new lower bound techniques; examines various different algorithmic solutions to the same problems, highlighting the insights to be gained from each approach; demonstrates how complexity methods and ideas have evolved over the past 25 years.

Recenzijas

It is a new book that conveys a detailed picture of parameterized complexity as it stands today. The writing style is direct and engaging, allowing the reader to quickly grasp the core ideas for each topic. The book coverage is comprehensive, including even relatively recent results, and manages to give a rich representation of the current state of the field. In short, this is an excellent book that will serve well anyone interested in algorithm design and complexity. (Marius Zimand, zbMATH 1358.68006, 2017)

It can be read by graduate students who have some background in computational complexity. I strongly recommend Fundamentals of Parameterized Complexity for all researchers in theoretical computer science. It is my belief that this book is now the definitive text on parameterized complexity, both for the breadthand depth of material covered and also for including the latest developments in the field (as recently as 2012). (Rajesh Chitnis, SIGACT News, Vol. 46 (1), 2015)

This book is currently the only monograph that covers lower bounds in kernelization or parameterized approximation. this new volume could serve as a (relatively easily) accessible source for a researcher in the area as well as helping students find their way into this interesting field. nearly 700 citations and a well-designed index help to navigate through the book and through the literature. (Henning Fernau, Mathematical Reviews, November, 2014)

Part I Parameterized Tractability
1 Preliminaries
3(12)
1.1 Basic Classical Complexity
3(4)
1.2 Advice Classes
7(2)
1.3 Valiant--Vazirani and BPP
9(3)
1.4 Historical Notes
12(1)
1.5 Summary
13(2)
2 The Basic Definitions
15(10)
2.1 The Basic Definition
15(1)
2.2 The Other Flavors of Parameterized Tractability
16(3)
2.3 Exercises
19(1)
2.4 Historical Notes
20(1)
2.5 Summary
21(4)
Part II Elementary Positive Techniques
3 Bounded Search Trees
25(24)
3.1 The Basic Method
25(1)
3.2 Vertex Cover
25(3)
3.2.1 A Basic Search Tree
25(1)
3.2.2 Shrinking the Search Tree
26(2)
3.3 Planar Independent Set
28(1)
3.4 Planar Dominating Set and Annotated Reduction Rules
29(4)
3.4.1 The Basic Analysis
29(2)
3.4.2 An Improved Analysis
31(2)
3.5 Feedback Vertex Set
33(3)
3.6 Closest String
36(1)
3.7 Jump Number and Scheduling
37(6)
3.8 Exercises
43(3)
3.9 Historical Notes
46(1)
3.10 Summary
47(2)
4 Kernelization
49(42)
4.1 The Basic Method
49(5)
4.2 Heuristics and Applications I
54(1)
4.3 Shrink the Kernel: The Nemhauser--Trotter Theorem
55(4)
4.4 Interleaving
59(1)
4.5 Heuristics and Applications II
60(2)
4.6 Heuristics and Applications III
62(1)
4.7 Definition of a Kernel
63(1)
4.8 k-Maximum Leaf Spanning Tree
64(3)
4.9 Hereditary Properties and Leizhen Cai's Theorem
67(2)
4.10 Maximum Agreement Forest
69(12)
4.10.1 Phylogeny
69(5)
4.10.2 The Algorithm and Correctness
74(7)
4.10.3 Analysis
81(1)
4.11 Exercises
81(7)
4.12 Historical Notes
88(1)
4.13 Summary
89(2)
5 More on Kernelization
91(16)
5.1 Turing Kernelization
91(9)
5.1.1 Rooted K-Leaf Outbranchtng
91(1)
5.1.2 s-t and r-r Numberings
92(3)
5.1.3 A Second Combinatorial Bound
95(1)
5.1.4 A Quadratic Kernel
96(3)
5.1.5 K-leaf Outbranching and Turing Kernels
99(1)
5.2 Crown Reductions
100(4)
5.3 Exercises
104(2)
5.4 Historical Notes
106(1)
5.5 Summary
106(1)
6 Iterative Compression, and Measure and Conquer, for Minimization Problems
107(24)
6.1 Iterative Compression: The Basic Technique
107(2)
6.2 Edge Bipartization
109(3)
6.3 Heuristics and Algorithmic Improvements
112(1)
6.4 Measure and Conquer
113(4)
6.5 Feedback Vertex Set
117(11)
6.5.1 The Simplified Algorithm
117(4)
6.5.2 The 3-Regular Case
121(4)
6.5.3 An Improved Running Time Using Measure and Conquer
125(3)
6.6 Exercises
128(1)
6.7 Historical Remarks
129(1)
6.8 Summary
130(1)
7 Further Elementary Techniques
131(12)
7.1 Methods Based on Induction
131(3)
7.1.1 The Extremal Method
131(1)
7.1.2 K-leaf Spanning Tree, Revisited
132(2)
7.2 Greedy Localization
134(3)
7.2.1 3-Dimensional Matching
135(2)
7.3 Bounded Variable Integer Programming
137(2)
7.4 Exercises
139(2)
7.5 Historical Notes
141(1)
7.6 Summary
141(2)
8 Color Coding, Multilinear Detection, and Randomized Divide and Conquer
143(28)
8.1 Introduction
143(1)
8.1.1 K-path
144(1)
8.1.2 Dynamic Programming
144(1)
8.2 The Randomized Technique
144(1)
8.3 De-randomizing
145(3)
8.3.1 Multidimensional Matching
147(1)
8.4 Speeding Things up with Multilinear Detection
148(5)
8.4.1 Group Algebras over Zk2
149(4)
8.5 Randomized Divide and Conquer
153(2)
8.6 Divide and Color
155(7)
8.6.1 The Algorithm and the Kernel
156(1)
8.6.2 Probability of a Good Coloring
157(1)
8.6.3 Solving a Colored Instance
158(2)
8.6.4 Derandomization with Universal Coloring Families
160(2)
8.7 Solving MAX-r-SAT Above a Tight Lower Bound
162(3)
8.8 Exercises
165(3)
8.9 Historical Notes
168(2)
8.10 Summary
170(1)
9 Optimization Problems, Approximation Schemes, and Their Relation to FPT
171(14)
9.1 Optimization
171(1)
9.2 Optimization Problems
171(1)
9.3 How FPT and Optimization Problems Relate: Part I
172(4)
9.4 The Classes MAX SNP, MIN F+ Π1(h) and FPT
176(5)
9.5 Exercises
181(1)
9.6 Historical Notes
182(1)
9.7 Summary
182(3)
Part III Techniques Based on Graph Structure
10 Treewidth and Dynamic Programming
185(20)
10.1 Basic Facts About Treewidth
185(4)
10.1.1 Introduction
185(1)
10.1.2 The Basic Definitions
186(3)
10.2 Exercises
189(1)
10.3 Algorithms for Graphs of Bounded Treewidth
190(3)
10.4 Exercises
193(2)
10.5 Bodlaender's Theorem
195(7)
10.6 Exercises
202(1)
10.7 Historical Notes
202(1)
10.8 Summary
203(2)
11 Heuristics for Treewidth
205(8)
11.1 Introduction
205(1)
11.2 Separators
206(1)
11.3 Perfect Elimination
207(2)
11.4 Reduction Rules
209(2)
11.5 Exercises
211(1)
11.6 Historical Notes
211(1)
11.7 Summary
211(2)
12 Methods via Automata and Bounded Treewidth
213(52)
12.1 Introduction
213(1)
12.2 Deterministic Finite Automata
213(3)
12.2.1 Historical Notes
216(1)
12.2.2 Exercises
216(1)
12.3 Nondeterministic Finite Automata
216(6)
12.3.1 Historical Notes
221(1)
12.3.2 Exercises
221(1)
12.4 Regular Languages
222(5)
12.4.1 Historical Notes
226(1)
12.4.2 Exercises
226(1)
12.5 The Myhill--Nerode Theorem and the Method of Test Sets
227(10)
12.5.1 Historical Notes
234(1)
12.5.2 Exercises
235(2)
12.6 Tree Automata
237(10)
12.6.1 Historical Notes
246(1)
12.6.2 Exercises
246(1)
12.7 Parse Trees for Graphs of Bounded Treewidth and an Analogue of the Myhill--Nerode Theorem
247(17)
12.7.1 Historical Notes
263(1)
12.7.2 Exercises
263(1)
12.8 Summary
264(1)
13 Courcelle's Theorem
265(14)
13.1 The Basic Theorem
265(7)
13.2 Implementing Courcelle's Theorem
272(1)
13.3 Seese's Theorem
272(2)
13.4 Notes on MS1 Theory
274(1)
13.5 Exercises
275(1)
13.6 Historical Notes
276(2)
13.7 Summary
278(1)
14 More on Width-Metrics: Applications and Local Treewidth
279(12)
14.1 Applications of Width Metrics to Objects Other than Graphs
279(5)
14.1.1 Logic
280(1)
14.1.2 Matroid Treewidth and Branchwidth
281(1)
14.1.3 Knots, Links, and Polynomials
282(2)
14.2 Local Treewidth
284(4)
14.2.1 Definitions
284(2)
14.2.2 The Frick--Grohe Theorem
286(2)
14.3 Exercises
288(1)
14.4 Historical Notes
288(1)
14.5 Summary
289(2)
15 Depth-First Search and the Plehn--Voigt Theorem
291(10)
15.1 Depth-First Search
291(2)
15.2 Exercises
293(2)
15.3 Bounded-Width Subgraphs, the Plehn--Voigt Theorem, and Induced Subgraphs
295(4)
15.4 Exercises
299(1)
15.5 Historical Remarks
300(1)
15.6 Summary
300(1)
16 Other Width Metrics
301(18)
16.1 Branchwidth
301(1)
16.2 Basic Properties of Branchwidth
302(1)
16.3 Dynamic Programming and Branchwidth
303(3)
16.4 Fast Matrix Multiplication and Dynamic Programming
306(3)
16.4.1 Improving Things Using Matrix Multiplication
307(2)
16.5 Cliquewidth and Rankwidth
309(3)
16.6 Directed Graphs
312(1)
16.7 d-Degeneracy
313(2)
16.8 Exercises
315(1)
16.9 Historical Notes
316(1)
16.10 Summary
316(3)
Part IV Exotic Meta-techniques
17 Well-Quasi-Orderings and the Robertson--Seymour Theorems
319(20)
17.1 Basics of Well-Quasi-Orderings Theory
319(14)
17.2 Connections with Automata Theory and Boundaried Graphs
333(3)
17.3 Exercises
336(1)
17.4 Historical Notes
337(1)
17.5 Summary
338(1)
18 The Graph Minor Theorem
339(12)
18.1 Introduction
339(1)
18.2 Excluding a Forest
340(2)
18.3 Thomas' Lemma
342(3)
18.4 The Graph Minor Theorem
345(2)
18.5 The Immersion and Topological Orders
347(1)
18.6 The Summary
348(1)
18.7 Exercises
349(1)
18.8 Historical Notes
350(1)
18.9 Summary
350(1)
19 Applications of the Obstruction Principle and WQOs
351(24)
19.1 Methods for Tractability
351(6)
19.2 Effectivizations of Obstruction-Based Methods
357(7)
19.2.1 Effectivization by Self-reduction
357(4)
19.2.2 Effectivization by Obstruction Set Computation
361(3)
19.3 The Irrelevant Vertex Technique
364(1)
19.4 Protrusions
365(4)
19.4.1 Informal Description
366(1)
19.4.2 Overview of the Protrusion Based Meta-kernelization Results
367(1)
19.4.3 Overview of the Methods
368(1)
19.5 Exercises
369(2)
19.6 Historical Remarks
371(1)
19.7 Summary
372(3)
Part V Hardness Theory
20 Reductions
375(8)
20.1 Introduction
375(2)
20.2 Parameterized Reductions
377(3)
20.3 Exercises
380(2)
20.4 Historical Notes
382(1)
20.5 Summary
382(1)
21 The Basic Class W[ 1] and an Analog of Cook's Theorem
383(24)
21.1 Introduction
383(1)
21.2 Short Turing Machine Acceptance
384(17)
21.3 Exercises
401(4)
21.4 Historical Notes
405(1)
21.5 Summary
406(1)
22 Some Other W[ 1] Hardness Results
407(20)
22.1 Perfect code and the Turing Way to W-Membership
407(5)
22.2 The VC Dimension
412(2)
22.3 Logic Problems
414(10)
22.4 Exercises
424(2)
22.5 Historical Notes
426(1)
22.6 Summary
426(1)
23 The W - Hierarchy
427(34)
23.1 Introduction
427(2)
23.2 The Normalization Theorem
429(15)
23.2.1 The Dominating Set Reduction
429(5)
23.2.2 The Proof of the Normalization Theorem
434(10)
23.3 Monotone and Antimonotone Formulas
444(2)
23.4 The W*-Hierarchy and Generalized Normalization to W*[ t]
446(9)
23.4.1 W* Normalization
447(1)
23.4.2 An Improved Characterization of W[ 1]
448(7)
23.5 Exercises
455(4)
23.6 Historical Notes
459(1)
23.7 Summary
459(2)
24 The Monotone and Antimonotone Collapse Theorems: Monotone W[ 2t + 1] = W[ 2t] and Antimonotone W[ 2t + 2] = W[ 2t + 1]
461(12)
24.1 Results
461(10)
24.2 Historical Notes
471(1)
24.3 Summary
471(2)
25 Beyond W[ t]-Hardness
473(18)
25.1 W[ P] and W[ Sat]
473(12)
25.2 Exercises
485(3)
25.3 Historical Remarks
488(1)
25.4 Summary
489(2)
26 Fixed Parameter Analogues of PSpace and k-Move Games
491(18)
26.1 Introduction
491(1)
26.2 k-Move Games
491(4)
26.3 AW[ *]
495(4)
26.4 Relational Databases
499(3)
26.5 Exercises
502(4)
26.6 Historical Notes
506(1)
26.7 Summary
507(2)
27 Provable Intractability: The Class XP
509(12)
27.1 Introduction and X Classes
509(1)
27.2 Pebble Games
510(7)
27.3 Other XP-Completeness Results
517(1)
27.4 Exercises
518(1)
27.5 Historical Remarks
518(1)
27.6 Summary
519(2)
28 Another Basis for the W-Hierarchy and the Tradeoff Theorem
521(14)
28.1 Results
521(9)
28.2 Exercises
530(1)
28.3 Historical Notes
531(1)
28.4 Summary
531(4)
Part VI Approximations, Connections, Lower Bounds
29 The M-Hierarchy, and XP-Optimality
535(36)
29.1 Introduction
535(1)
29.2 The W-Hierarchy and SubEXP Time
535(6)
29.3 The M-Hierarchy
541(1)
29.4 Parametric Miniatures
542(4)
29.5 The Sparsification Lemma
546(7)
29.5.1 Statement of the Lemma
546(1)
29.5.2 Using the Lemma for O*(2°(k)) Lower Bounds
546(6)
29.5.3 No O*((1 + ε)k) Algorithm for Vertex Cover
552(1)
29.6 The Proof of the Sparsification Lemma
553(3)
29.7 XP-Optimality
556(1)
29.8 Treewidth Lower Bounds
557(2)
29.9 The Strong Exponential Time Hypothesis
559(2)
29.10 Subexponential Algorithms and Bidimensionality
561(4)
29.11 Exercises
565(2)
29.12 Historical Notes
567(3)
29.12.1 Prehistory
567(2)
29.12.2 History
569(1)
29.13 Summary
570(1)
30 Kernelization Lower Bounds
571(52)
30.1 Introduction
571(1)
30.2 A Generic Engine for Lower Bounds of Kernels
572(5)
30.3 Applications of OR-Composition
577(2)
30.3.1 Notes on Turing Kernels
579(1)
30.4 And Composition
579(3)
30.5 Proof of Drucker's Theorem
582(6)
30.5.1 Statistical Distance and Distinguishability
582(1)
30.5.2 Proof of Theorem 30.5.2
583(5)
30.6 Cross-composition
588(4)
30.7 Unique Identifiers
592(3)
30.8 Sharpening Bounds
595(1)
30.9 The Packing Lemma
596(1)
30.10 Co-nondeterminism
597(9)
30.10.1 Co-nondeterministic Composition, and k-ramsey
597(5)
30.10.2 Co-nondeterministic Cross-composition and Hereditary Properties
602(4)
30.11 Weak Composition and Sharp Lower Bounds Revisited
606(6)
30.12 Miniature Parametric Miniatures
612(3)
30.13 Exercises
615(4)
30.14 Historical Notes
619(1)
30.15 Summary
619(4)
Part VII Further Topics
31 Parameterized Approximation
623(22)
31.1 Introduction
623(5)
31.2 Pathwidth
628(5)
31.3 Treewidth
633(2)
31.4 Parameterized Online Algorithms and Incremental Computing
635(4)
31.4.1 Coloring
636(1)
31.4.2 Online Coloring Graphs of Bounded Pathwidth
636(3)
31.5 Parameterized Inapproximability
639(2)
31.6 Exercises
641(2)
31.7 Historical Notes
643(1)
31.8 Summary
644(1)
32 Parameterized Counting and Randomization
645(32)
32.1 Introduction
645(1)
32.2 Classical Counting Problems and #P
646(2)
32.3 #W[ 1]---A Parameterized Counting Class
648(1)
32.4 The Counting Analog of Cook's Theorem
649(8)
32.5 The #W-Hierarchy
657(1)
32.6 An Analog of Valiant's Theorem
658(5)
32.7 Parameterized Randomization
663(7)
32.8 Exercises
670(1)
32.9 Historical Notes
671(2)
32.10 Summary
673(4)
Part VIII Research Horizons
33 Research Horizons
677(12)
33.1 The Most Infamous
677(2)
33.2 Think Positive!
679(2)
33.3 More Tough Customers
681(3)
33.4 Exemplars of Programs
684(5)
Part IX Appendices
34 Appendix 1: Network Flows and Matchings
689(16)
34.1 Network Flows
689(6)
34.1.1 Basic Results
689(2)
34.1.2 Exercises
691(1)
34.1.3 The Ford-Fulkerson Algorithm
692(1)
34.1.4 Matching Theory
693(2)
34.2 Berge's Criterion
695(2)
34.3 Edmonds' Algorithm
697(2)
34.4 Bipartite Graphs and vertex cover
699(1)
34.5 Matching and Co-graphic Matroids
700(4)
34.6 The Matroid Parity Problem
704(1)
35 Appendix 2: Menger's Theorems
705(4)
35.1 Connectivity
705(2)
35.2 Exercises
707(2)
References 709(36)
Index 745
Dr. Rodney G. Downey is a Professor in the School of Mathematics, Statistics and Operations Research, at the Victoria University of Wellington, New Zealand.

Dr. Michael R. Fellows is a Professor in the School of Engineering and Information Technology, at the Charles Darwin University, Darwin, NT, Australia.