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 |