zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
The Stanford GraphBase. A platform for combinatorial computing. (English) Zbl 0824.68040
Reading, MA: Addison-Wesley Publishing Company. vii, 576 p. (1994).

The Stanford GraphBase: A Platform for Combinatorial Computing is a book that is entertaining and instructive. It is partly a book about programming style and partly a book about combinatorial algorithms. Its use of some sophisticated algorithms will appeal to many theoreticians; and its constant theme that “Good programs are good literature” makes it of interest and importance to all computer scientists.

The GraphBase is built in the CWEB programming environment. It adds a library of CWEB programs and an extensive set of data, such as the graph of five letter English words with adjacency defined as differing in a single position; a graph of distances between American cities; graphs of relationships among characters in novels; and the like. It contains an extensive set of graph generators.

While its primary goal is not to treat all combinatorial algorithms, it deals with a large number of interesting ones: shortest paths, spanning trees, matching, strongly connected components and biconnected components, and De Launey triangulations are a few examples. It also treats basic combinatorial generation algorithms for partitions, combinations and permutations. In fact, second and third readings turn up more and more interesting algorithms and data structures.

I believe that the primary contribution of this book is to promote a certain style. Knuth interweaves clever program design, clear documentation, sophisticated algorithms, powerful data structures, and interesting applications – and he succeeds in making it fun.

Chapter 1 (Overview) describes the main modules of the GraphBase, and Chapter 2 (Technicalities) gives more detailed information about the problems addressed. Chapter 3 (Installation and Use) gives an introduction to CWEB and step-by-step instructions for its use and the installation of GraphBase.

The majority of the book is the actual code for the GraphBase. True to the author’s promise, the code is readable with ordinary effort. It is chock full of good ideas, and provides numerous useful techniques. The appendices then give some technical information.

This is not a conventional book about programming or about combinatorial algorithms. In Knuth’s presentation, both are shown by example. Consequently, it is a very valuable addition to the literature on both subjects.


MSC:
68Q10Modes of computation
68N01General theory of software
68W10Parallel algorithms
68-02Research monographs (computer science)
Software:
GraphBase