Contents

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