Search
Ordering block designs : gray codes, universal cycles and configuration orderings
Dewar M., Stevens B., Springer Publishing Company, Incorporated, New York, NY, 2012. 218 pp.  Type: Book (978-1-461443-24-7)
 Date Reviewed: Jan 23 2013
 A combinatorial block design is a mathematical object used in various engineering fields, such as experimental design, coding theory, and software testing, but also in other areas like tournament scheduling. A block design generally consists of a set of points P and a set of subsets of P, called blocks. The blocks are chosen to satisfy certain properties, such as symmetry or balance, which might be useful for an application. For example, in software testing, the points are all the possible input values. Since it might not be possible to run all input value combinations to test a new software version in one session, it becomes necessary to consider systematic differences of the value combinations in the various test runs. It might also be necessary to order the blocks, or parameter subsets, to systematically track down errors. This monograph focuses on ordered blocks where the difference between adjacent blocks is minimal. In coding theory, code with this property is known as Gray code (after Frank Gray, physicist and researcher); many of the results of coding theory can be used for ordering block designs. After a brief introduction, chapter 2 presents a good overview of designs in general and block designs in particular, especially the important class of balanced incomplete block designs. The authors next discuss binary and combinatorial Gray codes (chapter 3), and present more details on different orderings and configurations of block designs (chapter 4). In chapter 5, three different types of designs are discussed, and the existence of Gray codes and so-called universal cycles is proven for certain designs. This is the longest chapter in the book, and mathematically the most difficult one. Readers more oriented to applications may skip to chapter 6, the last chapter, where ordering block designs is applied to different problems, such as the correction of failures in redundant arrays of independent storage disks, the scheduling of game tournaments, reliability testing, and statistical experiments. Chapter 6, together with the background information in chapter 2, will interest engineers and scientific experimenters. The remainder of the book is only of interest to mathematical researchers in the field of combinatorial design theory. Each chapter includes some problem exercises (no solutions given) and a list of references. The authors have taken great care in explaining the mathematical formulae, using figures where applicable. Nonetheless, the presentation is dense and rigorous. This is not a book for beginners or readers looking for an introduction to combinatorial design. Reviewer:  Klaus Galensa Review #: CR140856 (1304-0287)
 Would you recommend this review? yes no
 Other reviews under "Combinatorics": Date Analytic combinatorics in several variablesPemantle R., Wilson M.,  Cambridge University Press, New York, NY, 2013. 400 pp. Type: Book (978-1-107031-57-9) Feb 21 2014 Approximation algorithms for a minimization variant of the order-preserving submatrices and for biclustering problemsHochbaum D., Levin A.  ACM Transactions on Algorithms 9(2): 1-12, 2013. Type: Article Jun 17 2013 Characterization of some 4-gonal configurations of Ahrens-Szekeres typeGhinelli D.  European Journal of Combinatorics 33(7): 1557-1573, 2012. Type: Article Jan 30 2013 more...

E-Mail This Printer-Friendly
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2014 ThinkLoud, Inc.