zbMATH — the first resource for mathematics

Algorithms and complexity. Handbook of theoretical computer science. Vol. A. (English) Zbl 0712.68054
Amsterdam etc.: Elsevier Science Publishers; Cambridge, MA: The MIT Press. IX, 996 p. Dfl. 275.00 (1990).

Show indexed articles as search result.

Here is an urgently needed (and gratefully received) book for researchers inside and outside the field of algorithms and complexity. Insiders may cross fertilize and outsiders may bring themselves up to speed with 18 chapters written by recognized experts. Each chapter supplies a bibliography, sometimes voluminous, and there is a comprehensive index for all chapters.
It would be difficult to pack this much material in a smaller space or, alternatively, to cram more material into the present one. In spite of the compactness of individual styles, most chapters succeed in being clear and readable. Here is a list of content with brief summaries:
“Machine models and simulations” by P. Van Emde Boas sets the stage by studying the relationships (via simulation) of various standard machine models.
“A catalog of complexity classes” by David S. Johnson covers the classic complexity classes with some theoretical updates as well as a tantalizing glimpse “inside P”: some p-time problems are not solvable in any practical sense.
“Machine-independent complexity theory” by J. I. Seiferas probes the issue of the “complexity” of a problem. Some problems have no least- complexity solution, after all. They may allow arbitrarily dramatic speed ups.
“Kolmogorov complexity and its applications” by M. Li and P. M. B. Vitanyi studies the information in a string in terms of the minimum- length program that will output it. Applications range from philosophical insights to the proof of lower bounds for some computations carried out by Turing machines.
“Algorithms for finding patterns in strings” by A. V. Aho examines the current status of investigation into the time-space tradeoffs in string searching. The theory includes the search for multiple keywords in a string.
“Data structures” by K. Mehlhorn and A. Tsakalidis covers the general “dictionary problem” which includes a review of the best results in search trees and hash tables. The literature on priority queues involves not only worst-case and average-case analyses, but “amortized analysis” applied to sequences of operations.
“Computational geometry” by F. F. Yao contains all the most efficient algorithms for geometrical problems such as line-segment intersection, convex hulls, nearest neighbors, minimum spanning trees, the TSP, clustering problems, linear programming, hidden surface removal and much more.
“Algorithmic motion planning in robotics” by J. T. Schwartz and M. Sharir covers the literature that addresses the problem of discovering the path that a given shape may take, from an initial to final position, through a space that contains various geometrical obstacles. There are no good optimality results in this field, apparently, except for the case of single-point motion.
“Average case analysis of algorithms and data structures” by J. S. Vitter and Ph. Flajolet obtains asymptotic estimates by setting up and solving recurrences that involve invariant time and space measures. Otherwise, one translates the combinatorial structure directly into a set of functional equations.
“Graph algorithms” by J. Van Leeuwen (the editor) can only hit the high spots in a voluminous literature for an ubiquitous combinatorial structure (graphs). The review is confined to sequential algorithms only. Typical topics include graph representation, traversal, transitive closure, graph generation, connectivity, shortest paths, disjoint paths, matchings, isomorphism testing and much else. Not surprisingly, this chapter has one of the largest bibliographies.
“Algorithms in number theory” by A. K. Lenstra and H. W. Lenstra, jr. reviews the literature on lower bounds for circuit complexity. The standard restrictions of bounded depth, gate types, or function types are included, as well as formula size as an alternative measure.
“Cryptography” by R. L. Rivest examines the relationship between cryptology, complexity and computational number theory. These days cryptographic systems are routinely proven to be secure. The chapter also covers the generation of “good” random sequences and the investigation of special protocols.
“The complexity of finite functions” by R. B. Boppana and M. Sipser reviews the literature on lower bounds for circuit complexity. The standard restrictions of bounded depth, gate types, or function types are included, as well as formula size as an alternative measure.
“Communication networks” by N. Pippenger surveys progress in the problem of connecting n “sources” to m “targets” via a network of minimum size (number of edges) or minimum depth. The chapter highlights the recent result by Aifai, Komlos and Szemeredi that a sorting network for n registers can be managed with depth O(log n).
“VLSI theory” by T. Lengauer reviews the study of various VLSI optimality criteria in limited layer circuity: communication time, wiring space, and switching energy. There is a formal definition of a “chip” and both lower and upper bounds on \(AT^ 2\) (area timesquared) complexity.
“Parallel algorithms for shared-memory machines” by R. M. Karp and V. Ramachandran defines a parallel random access machine (PRAM), then surveys studies of trade-offs between computation time and the number of processors. Of special interest is the polylog time measure in which computation time is bounded by a fixed power of the logarithm of input size.
“General purpose parallel architectures” by L. G. Valiant focuses on XPRAMs in which time proceeds in “supersteps” (each processor performs a limited number of steps). How quickly can the XPRAM model by implemented on various networks such as arbitrary graphs on the one hand, or hypercubes on the other?
For Part B see Zbl 0714.68001.
Reviewer: A.K.Dewdney

68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to computer science