search for books and compare prices
Tables of Contents for Combinatorial Algorithms
Chapter/Section Title
Page #
Page Count
1 Structures and Algorithms
1
30
1.1 What are combinatorial algorithms?
1
1
1.2 What are combinatorial structures?
2
5
1.2.1 Sets and lists
2
2
1.2.2 Graphs
4
1
1.2.3 Set systems
5
2
1.3 What are combinatorial problems?
7
2
1.4 O-Notation
9
1
1.5 Analysis of algorithms
10
3
1.5.1 Average-case complexity
12
1
1.6 Complexity classes
13
4
1.6.1 Reductions between problems
16
1
1.7 Data structures
17
6
1.7.1 Data structures for sets
17
5
1.7.2 Data structures for lists
22
1
1.7.3 Data structures for graphs and set systems
22
1
1.8 Algorithm design techniques
23
3
1.8.1 Greedy algorithms
23
1
1.8.2 Dynamic programming
24
1
1.8.3 Divide-and-conquer
25
1
1.9 Notes
26
1
Exercises
27
4
2 Generating Elementary Combinatorial Objects
31
36
2.1 Combinatorial generation
31
1
2.2 Subsets
32
11
2.2.1 Lexicographic ordering
32
3
2.2.2 Gray codes
35
8
2.3 k-Element subsets
43
9
2.3.1 Lexicographic ordering
43
2
2.3.2 Co-lex ordering
45
3
2.3.3 Minimal change ordering
48
4
2.4 Permutations
52
12
2.4.1 Lexicographic ordering
52
5
2.4.2 Minimal change ordering
57
7
2.5 Notes
64
1
Exercises
64
3
3 More Topics in Combinatorial Generation
67
38
3.1 Integer partitions
67
11
3.1.1 Lexicographic ordering
74
4
3.2 Set partitions, Bell and Stirling numbers
78
13
3.2.1 Restricted growth functions
81
6
3.2.2 Stirling numbers of the first kind
87
4
3.3 Labeled trees
91
4
3.4 Catalan families
95
8
3.4.1 Ranking and unranking
98
3
3.4.2 Other Catalan families
101
2
3.5 Notes
103
1
Exercises
103
2
4 Backtracking Algorithms
105
46
4.1 Introduction
105
2
4.2 A general backtrack algorithm
107
2
4.3 Generating all cliques
109
6
4.3.1 Average-case analysis
112
3
4.4 Estimating the size of a backtrack tree
115
3
4.5 Exact cover
118
4
4.6 Bounding functions
122
19
4.6.1 The knapsack problem
123
4
4.6.2 The traveling salesman problem
127
8
4.6.3 The maximum clique problem
135
6
4.7 Branch and bound
141
3
4.8 Notes
144
1
Exercises
145
6
5 Heuristic Search
151
40
5.1 Introduction to heuristic algorithms
151
5
5.1.1 Uniform graph partition
155
1
5.2 Design strategies for heauristic algorithms
156
9
5.2.1 Hill-climbing
157
1
5.2.2 Simulated annealing
158
2
5.2.3 Tabu search
160
1
5.2.4 Genetic algorithms
161
4
5.3 A steepest ascent algorithm for uniform graph partition
165
2
5.4 A hill-climbing algorithm for Steiner triple systems
167
8
5.4.1 Implementation details
170
4
5.4.2 Computational results
174
1
5.5 Two heuristic algorithms for the knapsack problem
175
6
5.5.1 A simulated annealing algorithm
175
3
5.5.2 A tabu search algorithm
178
3
5.6 A genetic algorithm for the traveling salesman problem
181
5
5.7 Notes
186
3
Exercises
189
2
6 Groups and Symmetry
191
46
6.1 Groups
191
4
6.2 Permutation groups
195
18
6.2.1 Basic algorithms
199
2
6.2.2 How to store a group
201
2
6.2.3 Schreier-Sims algorithm
203
8
6.2.4 Changing the base
211
2
6.3 Orbits of subsets
213
10
6.3.1 Burnside's lemma
214
3
6.3.2 Computing orbit representatives
217
6
6.4 Coset representatives
223
1
6.5 Orbits of k-tuples
224
2
6.6 Generating objects having automorphisms
226
6
6.6.1 Incidence matrices
227
5
6.7 Notes
232
1
Exercises
232
5
7 Computing Isomorphism
237
40
7.1 Introduction
237
1
7.2 Invariants
238
7
7.3 Computing certificates
245
27
7.3.1 Trees
245
8
7.3.2 Graphs
253
11
7.3.3 Pruning with automorphisms
264
8
7.4 Ismorphism of other structures
272
3
7.4.1 Using known automorphisms
272
1
7.4.2 Set systems
272
3
7.5 Notes
275
1
Exercises
275
2
8 Basis Reduction
277
34
8.1 Introduction
277
4
8.2 Theoretical development
281
10
8.3 A reduced basis algorithm
291
3
8.4 Solving systems of integer equations
294
6
8.5 The Markle-Hellman knapsack system
300
6
8.6 Notes
306
1
Exercises
307
4
Bibliography
311
8
Algorithm Index
319
4
Problem Index
323
2
Index
325