0.09 Preface 1 1 What is Combinatorial Computing? 2 1.1 An Example: Counting the Number of Ones in a Bit String 6 1.2 A Representation Problem: Difference-Preserving Codes 10 1.3 Composition Techniques 12 1.4 Decomposition Techniques 14 1.5 Classes of Algorythms 23 1.6 Analysis of Algorythms 28 1.7 Remarks and References 29 1.8 Exercises 32 2 Representation of Combinatorial Objects 32 2.1 Integers 35 2.2 Sequences 36 2.2.1 Sequential Allocation 38 2.2.2 Linked Allocation 41 2.2.3 Stacks and Queues 44 2.3 Trees 46 2.3.1 Representations 47 2.3.2 Traversals 52 2.3.3 Path Length 57 2.4 Sets and Multisets 64 2.5 Remarks and References 66 2.6 Exercises 71 3 Counting and Estimating 72 3.1 Asymptotics 77 3.2 Recurrence Relations 78 3.2.1 Linear Recurrence Relations with Constant Coefficients 82 3.2.2 General Recurrence Relations 86 3.3 Generating Functions 92 3.4 Counting Equivalence Classes: Polya's Theorem 93 3.4.1 An Example: Coloring the Nodes of a Binary Tree 96 3.4.2 Polya's Theorem and Burnside's Lemma 99 3.5 Remarks and References 100 3.6 Exercises 106 4 Exhaustive Search 107 4.1 Backtrack 107 4.1.1 The Generated Algorithm 110 4.1.2 Refinements 112 4.1.3 Estimation of Performance 114 4.1.4 Two Programming Techniques 116 4.1.5 An Example: Optimal Difference-Preserving Codes 121 4.1.6 Branch and Bound 130 4.1.7 Dynamic Programming 134 4.2 Sieves 134 4.2.1 Nonrecursive Modular Sieves 138 4.2.2 Recursive Sieves 140 4.2.3 Isomorph-Rejection Sieves 141 4.3 Approximation to Exahustive Search 148 4.4 Remarks and References 151 4.5 Exercises 159 5 Generating Elementary Combinatorial Objects 161 5.1 Permutations of Distincts Elements 161 5.1.1 Lexicographic Order 164 5.1.2 Inversion Vectors 165 5.1.3 Nested Cycles 168 5.1.4 Transposition of Adjacent Elements 171 5.1.5 Random Permutations 172 5.2 Subsets of Sets 173 5.2.1 Gray Codes 179 5.2.2 k Subsets (Combinations) 190 5.3 Compositions and Partitions of Integers 190 5.3.1 Compositions 191 5.3.2 Partitions 196 5.4 Remarks and References 199 5.5 Exercises 204 6 Fast Search 204 6.1 Searching and Other Operations on ables 208 6.2 Sequential Search 212 6.3 Logarithmic Search in Static Tables 213 6.3.1 Binary Search 216 6.3.2 Optimal Binary Search Trees 224 6.3.3 Near-Optimal Binary Search Trees 228 6.3.4 Digital Search 232 6.4 Logarithmic Search in Dynamic Tables 233 6.4.1 Random Binary Search Trees 235 6.4.2 Height-Balanced Binary Trees 243 6.4.3 Weight-Balanced Binary Trees 251 6.4.4 Balanced Multiway Trees 255 6.5 Address Computation Techniques 256 6.5.1 Hashing and its Variants 260 6.5.2 Hash Functions 262 6.5.3 Collision Resolution 264 6.5.4 The Influence of the Load Factor 266 6.6 Remarks and References 270 6.7 Exercises 277 7 Sorting 278 7.1 Internal Sorting 281 7.1.1 Insertion 283 7.1.2 Transposition Sorting 290 7.1.3 Selection 295 7.1.4 Distribution 297 7.2 External Sorting 302 7.3 Partial Sorting 304 7.3.2 Merging 308 7.4 Remarks and References 310 7.5 Exercises 318 8 Graph Algorithms 322 8.2 Connectivity and Distance 323 8.2.1 Spanning Trees 327 8.2.2 Depth-First Search 331 8.2.3 Biconenctivity 334 8.2.4 Strong Connectivity 338 8.2.5 Transitive Closure 341 8.2.6 Shortest Paths 346 8.3 Cycles 346 8.3.1 Fundamental Sets of Cycles 348 8.3.2 Generating All Cycles 353 8.4 Cliques 359 8.5 Isomorphism 364 8.6 Planarity 385 8.7 Remarks and References 392 8.8 Exercises 401 9 The Equivalence of Certain Combinatorial Problems 401 9.1 The Classes P and NP 405 9.2 NP-Hard and NP-Complete Problems 406 9.2.1 Satisfiability 409 9.2.2 Some NP-Complete Problems 414 9.2.3 The Travelling Salesman Problem Revisited 416 9.3 Remarks and References 420 9.4 Exercises 423 Index
1900 1900
2000 2000
1950 2050 Reingold, Edward M. ( - ) Reingold, Edward M. ( - ) Reingold, Edward M.
Nievergelt, Jurg ( - ) Nievergelt, Jurg ( - ) Nievergelt, Jurg
Deo, Narsingh ( - ) Deo, Narsingh ( - ) Deo, Narsingh
1877 4523.0412 1977
