Combinatorial algorithms: generation, enumeration, and search

Cover......Page 1
Title Page......Page 4
Copyright Page......Page 5
Preface......Page 6
Dedication......Page 8
Table of Contents......Page 10
 1.1 What are Combinatorial Algorithms?......Page 14
  1.2.1 Sets and Lists......Page 15
  1.2.2 Graphs......Page 17
  1.2.3 Set Systems......Page 18
 1.3 What are Combinatorial Problems?......Page 20
 1.4 O-Notation......Page 22
 1.5 Analysis of Algorithms......Page 23
  1.5.1 Average-Case Complexity......Page 25
 1.6 Complexity Classes......Page 26
  1.6.1 Reductions Between Problems......Page 29
  1.7.1 Data structures for sets......Page 30
  1.7.3 Data Structures for Graphs and Set Systems......Page 35
  1.8.1 Greedy Algorithms......Page 36
  1.8.2 Dynamic Programming......Page 37
  1.8.3 Divide-and-Conquer......Page 38
 1.9 Notes......Page 39
 Exercises......Page 40
 2.1 Combinatorial Generation......Page 44
  2.2.1 Lexicographic Ordering......Page 45
  2.2.2 Gray Codes......Page 48
  2.3.1 Lexicographic Ordering......Page 56
  2.3.2 Co-lex Ordering......Page 58
  2.3.3 Minimal Change Ordering......Page 61
  2.4.1 Lexicographic Ordering......Page 65
  2.4.2 Minimal Change Ordering......Page 70
 Exercises......Page 77
 3.1 Integer Partitions......Page 80
  3.1.1 Lexicographic Ordering......Page 87
 3.2 Set Partitions, Bell and Stirling Numbers......Page 91
  3.2.1 Restricted Growth Functions......Page 94
  3.2.2 Stirling Numbers of the First Kind......Page 100
 3.3 Labeled Trees......Page 104
 3.4 Catalan Families......Page 108
  3.4.1 Ranking and Unranking......Page 111
  3.4.2 Other Catalan Families......Page 114
 3.5 Notes......Page 116
 4.1 Introduction......Page 118
 4.2 A General Backtrack Algorithm......Page 120
 4.3 Generating All Cliques......Page 122
  4.3.1 Average-Case Analysis......Page 125
 4.4 Estimating the Size of a Backtrack Tree......Page 128
 4.5 Exact Cover......Page 131
 4.6 Bounding Functions......Page 135
  4.6.1 The Knapsack Problem......Page 136
  4.6.2 The Traveling Salesman Problem......Page 140
  4.6.3 The Maximum Clique Problem......Page 148
 4.7 Branch and Bound......Page 154
 4.8 Notes......Page 157
 Exercises......Page 158
 5.1 Introduction to Heuristic Algorithms......Page 164
  5.1.1 Uniform Graph Partition......Page 168
 5.2 Design Strategies for Heuristic Algorithms......Page 169
  5.2.1 Hill-Climbing......Page 170
  5.2.2 Simulated Annealing......Page 171
  5.2.3 Tabu Search......Page 173
  5.2.4 Genetic Algorithms......Page 174
 5.3 A Steepest Ascent Algorithm for Uniform Graph Partition......Page 178
 5.4 A Hill-Climbing Algorithm for Steiner Triple Systems......Page 180
  5.4.1 Implementation Details......Page 183
  5.4.2 Computational Results......Page 187
  5.5.1 A Simulated Annealing Algorithm......Page 188
 5.6 A Genetic Algorithm for the Traveling Salesman Problem......Page 194
 5.7 Notes......Page 199
 Exercises......Page 202
 6.1 Groups......Page 204
 6.2 Permutation Groups......Page 208
  6.2.1 Basic Algorithms......Page 212
  6.2.2 How to Store a Group......Page 214
  6.2.3 Schreier-Sims Algorithm......Page 216
  6.2.4 Changing the Base......Page 224
 6.3 Orbits of Subsets......Page 226
  6.3.1 Burnside’s Lemma......Page 227
  6.3.2 Computing Orbit Representatives......Page 230
 6.4 Coset Representatives......Page 236
 6.5 Orbits of к-Tuples......Page 237
 6.6 Generating Objects Having Automorphisms......Page 239
  6.6.1 Incidence Matrices......Page 240
 Exercises......Page 245
 7.1 Introduction......Page 250
 7.2 Invariants......Page 251
  7.3.1 Trees......Page 258
  7.3.2 Graphs......Page 266
  7.3.3 Pruning with Automorphisms......Page 277
  7.4.2 Set Systems......Page 285
 Exercises......Page 288
 8.1 Introduction......Page 290
 8.2 Theoretical Development......Page 294
 8.3 A Reduced Basis Algorithm......Page 304
 8.4 Solving Systems of Integer Equations......Page 307
 8.5 The Merkle-Hellman Knapsack System......Page 313
 8.6 Notes......Page 319
 Exercises......Page 320
Bibliography......Page 324
Algorithm Index......Page 332
Problem Index......Page 336
Index......Page 338