Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0824.68040
Knuth, Donald E.
The Stanford GraphBase. A platform for combinatorial computing. (English)
[B] Reading, MA: Addison-Wesley Publishing Company. vii, 576 p. (1994). ISBN 0-201-54275-7/hbk

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.\par 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.\par 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.\par 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.\par 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.\par 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.\par 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.
[C.J.Colbourn (Waterloo / Ontario)]

MSC 2000:: *68Q10 Modes of computation
68N01 General
68W10 Parallel algorithms
68-02 Research monographs (computer science)

Keywords: combinatorial algorithms

Cited in: Zbl 1198.68147

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]