Invitation to fixed-parameter algorithmspdf电子书版本下载

点此进入-本书在线PDF格式电子书下载【推荐-云解压-方便快捷】直接下载PDF格式图书。移动端-PC端通用
种子下载[BT下载速度快] 温馨提示：（请使用BT下载软件FDM进行下载）软件下载地址页 直链下载[便捷但速度慢]   [在线试读本书]   [在线获取解压码]

Invitation to fixed-parameter algorithmsPDF格式电子书版下载

下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。

建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！

（文件页数 要大于 标注页数，上中下等多册电子书除外）

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Ⅰ FOUNDATIONS 3

1 Introduction to Fixed-Parameter Algorithms 3

1.1 The satisfiability problem 4

1.2 An example from railway optimization 7

1.3 A communication problem in tree networks 10

1.4 Summary 12

1.5 Exercises 13

1.6 Bibliographical remarks 14

2 Preliminaries and Agreements 17

2.1 Basic sets and problems 17

2.2 Model of computation and running times 17

2.3 Strings and graphs 18

2.4 Complexity and approximation 20

2.5 Bibliographical remarks 21

3 Parameterized Complexity Theory —A Primer 22

3.1 Basic theory 22

3.2 Interpreting fixed-parameter tractability 27

3.3 Exercises 29

3.4 Bibliographical remarks 29

4 Vertex Cover An Illustrative Example 31

4.1 Parameterizing 32

4.2 Specializing 33

4.3 Generalizing 34

4.4 Counting or enumerating 34

4.5 Lower bounds 35

4.6 Implementing and applying 35

4.7 Using vertex cover structure for other problems 36

4.8 Exercises 38

4.9 Bibliographical remarks 38

5 The Art of Problem Parameterization 41

5.1 Parameter really small？ 41

5.2 Guaranteed parameter value？ 42

5.3 More than one obvious parameterization？ 43

5.4 Close to “trivial” problem instances？ 45

5.5 Exercises 47

5.6 Bibliographical remarks 47

6 Summary and Concluding Remarks 49

Ⅱ ALGORITHMIC METHODS 53

7 Data Reduction and Problem Kernels 53

7.1 Basic definitions and facts 55

7.2 Maximum Satisfiability 58

7.3 Cluster Editing 60

7.4 Vertex Cover 64

7.4.1 Kernelization based on matching 64

7.4.2 Kernelization based on linear programming 68

7.4.3 Kernelization based on crown structures 69

7.4.4 Comparison and discussion 72

7.5 3-Hitting Set 72

7.6 Dominating Set in Planar Graphs 74

7.6.1 The neighborhood of a single vertex 74

7.6.2 The neighborhood of a pair of vertices 77

7.6.3 Reduced graphs and the problem kernel 79

7.7 On lower bounds for problem kernels 80

7.8 Summary and concluding remarks 82

7.9 Exercises 83

7.10 Bibliographical remarks 85

8 Depth-Bounded Search Trees 88

8.1 Basic definitions and facts 91

8.2 Cluster Editing 93

8.3 Vertex Cover 98

8.4 Hitting Set 101

8.5 Closest String 103

8.6 Dominating Set in Planar Graphs 107

8.6.1 Data reduction rules 108

8.6.2 Main result and some remarks 109

8.7 Interleaving search trees and kernelization 110

8.7.1 Basic methodology 111

8.7.2 Interleaving is necessary 113

8.8 Automated search tree generation and analysis 114

8.9 Summary and concluding remarks 119

8.10 Exercises 120

8.11 Bibliographical remarks 121

9 Dynamic Programming 124

9.1 Basic definitions and facts 125

9.2 Knapsack 126

9.3 Steiner Problem in Graphs 128

9.4 Multicommodity Demand Flow in Trees 131

9.5 Tree-structured variants of Set Cover 136

9.5.1 Basic definitions and facts 136

9.5.2 Algorithm for Path-like Weighted Set Cover 139

9.5.3 Algorithm for Tree-like Weighted Set Cover 140

9.6 Shrinking search trees 145

9.7 Summary and concluding remarks 146

9.8 Exercises 147

9.9 Bibliographical remarks 148

10 Tree Decompositions of Graphs 150

10.1 Basic definitions and facts 151

10.2 On the construction of tree decompositions 153

10.3 Planar graphs 155

10.4 Dynamic programming for Vertex Cover 160

10.5 Dynamic programming for Dominating Set 164

10.6 Monadic second-order logic （MSO） 169

10.7 Related graph width parameters 172

10.8 Summary and concluding remarks 174

10.9 Exercises 175

10.10Bibliographical remarks 176

11 Further Advanced Techniques 177

11.1 Color-coding 178

11.2 Integer linear programming 181

11.3 Iterative compression 184

11.3.1 Vertex Cover 185

11.3.2 Feedback Vertex Set 187

11.4 Greedy localization 190

11.4.1 Set Splitting 191

11.4.2 Set Packing 193

11.5 Graph minor theory 195

11.6 Summary and concluding remarks 197

11.7 Exercises 198

11.8 Bibliographical remarks 199

12 Summary and Concluding Remarks 201

Ⅲ SOME THEORY，SOME CASE STUDIES 205

13 Parameterized Complexity Theory 205

13.1 Basic definitions and concepts 206

13.1.1 Parameterized reducibility 207

13.1.2 Parameterized complexity classes 209

13.2 The complexity class W[1] 212

13.3 Concrete parameterized reductions 216

13.3.1 W [1]-hardness proofs 218

13.3.2 Further reductions and W[2]-hardness 226

13.4 Some recent developments 230

13.4.1 Lower bounds and the complexity class M[1] 230

13.4.2 Lower bounds and linear FPT reductions 232

13.4.3 Machine models，limited nondeterminism，and bounded FPT 233

13.5 Summary and concluding remarks 234

13.6 Exercises 235

13.7 Bibliographical remarks 235

14 Connections to Approximation Algorithms 237

14.1 Approximation helping parameterization 238

14.2 Parameterization helping approximation 239

14.3 Further （non-）relations 241

14.4 Discussion and concluding remarks 241

14.5 Bibliographical remarks 242

15 Selected Case Studies 243

15.1 Planar and more general graphs 243

15.1.1 Planar graphs 243

15.1.2 More general graphs 245

15.2 Graph modification problems 245

15.2.1 Graph modification and hereditary properties 246

15.2.2 Feedback Vertex Set revisited 247

15.2.3 Graph Bipartization 248

15.2.4 Minimum Fill-In 249

15.2.5 Closest 3-Leaf Power 250

15.3 Miscellaneous graph problems 251

15.3.1 Capacitated Vertex Cover 251

15.3.2 Constraint Bipartite Vertex Cover 253

15.3.3 Graph Coloring 255

15.3.4 Crossing Number 256

15.3.5 Power Dominating Set 257

15.4 Computational biology problems 258

15.4.1 Minimum Quartet Inconsistency 259

15.4.2 Compatibility of Unrooted Phylogenetic Trees 261

15.4.3 Longest Arc-Preserving Common Subsequences 262

15.4.4 Incomplete Perfect Path Phylogeny Haplotyp-ing 264

15.5 Logic and related problems 266

15.5.1 Satisfiability 266

15.5.2 Maximum Satisfiability 268

15.5.3 Constraint satisfaction problems 269

15.5.4 Database queries 270

15.6 Miscellaneous problems 271

15.6.1 Two-dimensional Euclidean TSP 272

15.6.2 Multidimensional matching 273

15.6.3 Matrix Domination 273

15.6.4 Vapnik-Chervonenkis Dimension 274

15.7 Summary and concluding remarks 275

16 Zukunftsmusik 277

References 279

Index 294