Our objective in writing this book was to produce a general, introductory textbook on the subject of combinatorial algorithms. Several textbooks on combinatorial algorithms were written in the 1970s, and are now out-of-date. More recent books on algorithms have either been general textbooks, or books on specialized topics, such as graph algorithms to name one example. We felt that a new textbook on combinatorial algorithms, that emphasizes the basic techniques of generation, enumeration and search, would be very timely.
We have both taught courses on this subject, to undergraduate and graduate students in mathematics and computer science, at Michigan Technological University and the University of Nebraska-Lincoln. We tried to design the book to be flexible enough to be useful in a wide variety of approaches to the subject.
We have provided a reasonable amount of mathematical background
where it is needed, since an understanding of the algorithms
is not possible without an understanding of the underlying
mathematics.
We give informal descriptions
of the many algorithms in this book, along with more precise pseudo-code
that can easily be converted to working programs.
C implementations of all the algorithms are
available for free downloading from the
website
http://www.math.mtu.edu/kreher/cages.html
There are also many examples in the book to illustrate the workings of the algorithms.
The book is organized into eight chapters. Chapter 1 provides some background and notation for fundamental concepts that are used throughout the book. Chapters 2 and 3 are concerned with the generation of elementary combinatorial objects such as subsets and permutations, to name two examples. Chapter 4 presents the important combinatorial search technique called backtracking. It includes a discussion of pruning methods, and the maximum clique problem is studied in detail. Chapter 5 gives an overview of the relatively new area of heuristic search algorithms, including hill-climbing, simulated annealing, tabu search and genetic algorithms. In Chapter 6, we study several basic algorithms for permutation groups, and how they are applied in solving certain combinatorial enumeration and search problems. Chapter 7 uses techniques from the previous chapter to develop algorithms for testing isomorphism of combinatorial objects. Finally, Chapter 8 discusses the technique of basis reduction, which is an important technique in solving certain combinatorial search problems.
There is probably more material in this book than can be covered in one semester. We hope that it is possible to base several different types of courses on this book. An introductory course suitable for undergraduate students could cover most of the material in Chapters 1-5. A second or graduate course could concentrate on the more advanced material in Chapters 6-8. We hope that, aside from its primary purpose as a textbook, researchers and practitioners in all areas of combinatorial computing will find this book useful as a source of algorithms for practical use.
We would like to thank the many people who provided encouragement while we wrote this book, pointed out typos and errors, and gave us useful suggestions on material to include and how various topics should be treated. In particular, we would like to convey our thanks to Mark Chateauneuf, Charlie Colbourn, Bill Kocay, François Margot, Wendy Myrvold, David Olson, Partic Östergård, Jamie Radcliffe, Stanisaw Radziszowski and Mimi Williams.
Donald L. Kreher
Douglas R. Stinson