Ebook: Combinatorial algorithms : generation, enumeration, and search

"This textbook thoroughly outlines combinatorial algorithms for generation, enumeration, and search. Topics include backtracking and heuristic search methods, applied to various combinatorial structures, such as combinations, permutations, graphs, and designs." "Many classical areas are covered as well as new research topics not included in most existing texts such as group algorithms, graph isomorphism, Hill climbing, and heuristic search algorithms."--BOOK JACKET. Read more... 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 -- 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 -- 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 -- 4 Backtracking Algorithms 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 -- 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 -- 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 -- 7 Computing Isomorphism 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 -- 8 Basis Reduction 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