The Stanford GraphBase: A Platform for Combinatorial Computing

The Stanford GraphBase: A Platform for Combinatorial Computing by Knuth, Donald E.. hardcover edition. ISBN: 0785342542752.

The Stanford GraphBase: A Platform for Combinatorial Computing represents the first fruits of Donald E. Knuths preparation for Volume 4 of The Art of Computer Programming. The books first goal is to demonstrate, through about 30 examples, the art of literate programming. Each example is a programmatic essay, a short story that can be read and enjoyed by human beings as readily as it can be read and interpreted by machines. In these essays/programs, Knuth makes new contributions to the exposition of several important algorithms and data structures, so the programs are of special interest for their content as well as for their style. The books second goal is to provide a useful means for comparing combinatorial algorithms and for evaluating methods of combinatorial computing. To this end, Knuths programs offer standard freely available sets of data - the Stanford GraphBase - that may be used as benchmarks to test competing methods. The data sets are both interesting in themselves and applicable to a wide variety of problem domains. With objective tests here made possible, Knuth hopes to bridge the gap between theoretical computer scientists and programmers who have real problems to solve. As with all of Knuths writings, this book is appreciated not only for the authors unmatched insight, but also for the fun and the challenge of his work, in which he invites us to participate. He illustrates many of the most significant and most beautiful combinatorial algorithms that are presently known and provides demonstration programs that can lead to hours of amusement. In showing how the Stanford GraphBase can generate an almost exhaustible supply of challenging problems, some of which may lead to the discovery of new and improved algorithms, Knuth proposes friendly competitions. His own initial entries into such competitions are included in the book, and readers are challenged to do better.