You are here

Graphs, Algorithms, and Optimization

William Kocay and Donald L. Kreher
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2004
Number of Pages: 
483
Format: 
Hardcover
Series: 
Discrete Mathematics and Its Applications
Price: 
89.95
ISBN: 
1584883960
Category: 
Monograph
[Reviewed by
Frederick M. Butler
, on
02/1/2005
]

Graphs, Algorithms and Optimization, by William Kocay and Donald L. Kreher, was written as a textbook for computer science majors in an upper division or graduate level course on graph theory involving some programming. This book covers a wide variety of elementary graph theory topics, including bipartite graphs, trees, connectivity, Euler tours, Hamiltonian cycles, digraphs, graph coloring, and planarity. In addition there is a very interesting chapter about graphs on surfaces, and three chapters treating topics in linear programming.

The book is written in an easygoing style, and the proofs are concisely presented and easy to follow. The figures are also clearly drawn and are well utilized to illustrate key concepts and arguments in proofs. The exercises do a good job guiding students through examples to illustrate important definitions and theorems. I do think the exercises might be a bit challenging to a student with a weak background in either the basics graph theory or general mathematical proof techniques — perhaps an appendix with hints or solutions would be a nice addition.

This book seems to be well-suited to its intended purpose for upper division computer science majors (with a reasonable math background). The authors describe all of the algorithms discussed using such general programming constructs as if-then statements, for loops, and while loops, not tied to any specific programming language. While most of the "pseudocode" the authors use is self-explanatory, some of the more complex algorithms can look a little overwhelming written in this way. This is something most upper division computer science majors will be familiar with, and they will have little trouble understanding the algorithms.

As a final remark, I think Graphs, Algorithms and Optimization would serve as a fine textbook for an undergraduate graph theory course for math majors. I believe that even students with little or no programming background could learn a lot of mathematics from this book, especially if the instructor were to place minimal emphasis on the programming and pseudocode algorithms. All the positive comments made earlier about the book — that it is well-written, the proofs are easy to follow, the figures complement the text, and the exercises are helpful to student understanding — in my opinion make it a strong choice for this purpose as well.


Frederick M. Butler is Assistant Professor of Mathematics at the Institute for Mathematics Learning, West Virginia University.

The table of contents is not available.