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