Recent research results on reconfiguration problems in VLSI and wafer-scale integration (WSI) systems are reported. The goal of this research was to develop efficient algorithms for the fault covering approach. In the first chapter, a good overview of the domain is given, including an explanation of both approaches to the general problem: the covering and embedding approaches. The covering approach is the subject of the theory developed in this work, as it is technically and economically the most interesting at present. The second chapter addresses the problem of finding fault covers in rectangular arrays with a fixed set of spare rows and columns, all with identical elements. A strategy to reduce the number of solutions to be investigated for this problem in an exhaustive search approach is developed, and experimental results on standard benchmarks for this type of problem are given. A generalization of the model to reconfiguration with shared spaces (with application to programmable logic arrays) is given.

Chapter 3 investigates the fault covering problem in arrays with heterogeneous elements. Polynomial-time algorithms are given for two classes of subproblems. An application of this type of model is reconfigurable stacks of arrays. In the last section, a general reconfigurable array model is developed that includes both the homogeneous and the heterogeneous array models investigated before; this model leads to insight into the complexity of the algorithms to compute covers under different conditions. In chapter 4, the relationship between faulty and spare elements, until then considered to be structured by rows and columns, is generalized into a formulation that is shown to be transformable into an integer linear programming problem. This approach allows the authors to build on the set of methods and tools developed for this specific problem (which has been shown to be NP-complete).

This work is a well-structured overview of the authors’ research in this domain, which requires a lot of background knowledge on algorithms and the complexity of algorithms to be understood. The illustration with concrete examples after many steps shows that practical applications guided the work, which nevertheless is formulated in a mathematical terminology. The work is rather condensed; for nonspecialists to study it thoroughly, they will need to consult a number of references.

The best feature of the work is that it is well structured (in the sense of a mathematical theory), evolving from a limited model (all elements identical, arranged in a rectangular grid) to a general theory with interesting applications. As such the work is good, though probably only useful to a limited audience due to its condensed writing style. The intended audience is therefore researchers in this particular field and people interested in algorithmic aspects of VLSI design, of which this work is a good illustration. It would be difficult to use this text as a classroom textbook. A good background in algorithmics and complexity analysis of algorithms is required. The references are good and broad, allowing the reader to start a literature survey in any direction related to the work.