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