Combinatorial search.

*(English)*Zbl 0663.68076
Wiley-Teubner Series in Computer Science. Stuttgart (FRG): B. G. Teubner; Chichester (UK): Wiley. 368 p.; DM 58.00 (1988).

Issues of “searching” are of paramount importance in information processing. In bare essence, the goal is to find an object(s), satisfying a certain property, in as short a time as possible or with as little cost as possible. In this book the author presents an introduction to the basic ideas (Chapter 1) and discusses some interesting instances (Chapters 2-6) of combinatorial search problems.

The first chapter (“Basic results”) sets up the model for the general search process and develops some methods for solving concrete problems. Chapter 2 (“Weighing problems”) deals in some detail with two weighing models, the balance scale and the spring scale. The two models are shown to be quite different and are then generalized in some interesting ways. Chapter 3 (“Graph problems”) presents several search problems in graphs. Included are edge searching, Aanderaa-Rosenberg conjecture and its solution by Rivest and Vuillemin. In Chapter 4 (“Sorting problems”) various variants of sorting are discussed. Among these are merging, selection, sorting networks and parallel sorting. Chapter 5 (“Poset problems”) generalizes the basic ideas of Chapter 4. When manipulating an ordered set our knowledge can be represented by a poset. General results on posets and lattices can provide deep insights into various sorting problems. The last chapter collects several topics that received some more recent attention. The connection of search problems with notions from algebra and geometry is investigated. This includes a discussion of polyhedral membership problem, coloring and chromatic polynomials.

The book is a much needed up-to-date overview of the subject of combinatorial search. It stresses the connections with information theory, ordered structures and graphs. Each chapter contains many exercises and a portion of these are solved in a special appendix; at the end of each chapter the author gives a list of open problems and an annotated bibliography for the topics covered in that chapter. The book can serve as an excellent introduction to research in combinatorial search theory.

The first chapter (“Basic results”) sets up the model for the general search process and develops some methods for solving concrete problems. Chapter 2 (“Weighing problems”) deals in some detail with two weighing models, the balance scale and the spring scale. The two models are shown to be quite different and are then generalized in some interesting ways. Chapter 3 (“Graph problems”) presents several search problems in graphs. Included are edge searching, Aanderaa-Rosenberg conjecture and its solution by Rivest and Vuillemin. In Chapter 4 (“Sorting problems”) various variants of sorting are discussed. Among these are merging, selection, sorting networks and parallel sorting. Chapter 5 (“Poset problems”) generalizes the basic ideas of Chapter 4. When manipulating an ordered set our knowledge can be represented by a poset. General results on posets and lattices can provide deep insights into various sorting problems. The last chapter collects several topics that received some more recent attention. The connection of search problems with notions from algebra and geometry is investigated. This includes a discussion of polyhedral membership problem, coloring and chromatic polynomials.

The book is a much needed up-to-date overview of the subject of combinatorial search. It stresses the connections with information theory, ordered structures and graphs. Each chapter contains many exercises and a portion of these are solved in a special appendix; at the end of each chapter the author gives a list of open problems and an annotated bibliography for the topics covered in that chapter. The book can serve as an excellent introduction to research in combinatorial search theory.

Reviewer: G.Slutzki