MAA Reviews

<< homepage

 

show printer friendly

send to a friend

Algorithmic Graph Theory

See the table of contents

This book is in the MAA's basic library list.

MAA Review

The book addresses standard topics on graph theory, with a strong bias toward the algorithmic standpoint, caring about implementation details that are often neglected or simply overlooked. (A few such remain, such as "stack something if it has not already been stacked" and others). The pseudo-codes, quite carefully written in general, are very close to actual high-level programming languages, and can be counted among the main strengths of the text. Another nice aspect related to the algorithms' presentation is the step-by-step simulation of their execution, which can be found every now and then throughout the book.

In the introductory chapter, there is a brief discussion of complexity issues, with time estimates given in actual seconds, minutes, hours, etc., and motivated by real-world scenarios. The last chapter of the book also provides an easy, yet not shallow, account of complexity classes and NP-completeness theory.

The exercises, at the end of every chapter, are very well chosen and/or devised, with a large number of unorthodox formulations that lend them an extra dose of interest. Some particularly elucidative exercises ask the reader to find counterexamples to certain unsound (albeit intuitive) "algorithms". Unlike many other textbooks, no parts of lengthy proofs are left as exercises. The exercises almost always deal with suitable applications of the theory covered in each chapter.

Another plus of the text is the fact that the proofs of well-known theorems do not just follow the original papers, but rather are simpler or more straightforward. The chapter on planarity, for instance, is very nice, and gives an utterly clear proof of Kuratowski's theorem.

There is not much to be talked about on the minus side: there are some slight inconsistencies in the indentation of some pieces of code, which however never compromise understandability. Bibliographical references are comprehensive enough, but they could perhaps be updated with post-1985 entries in future editions. Some figures have no captions, whereas many others do. Captions are helpful for returning readers who may want to remember central ideas of algorithms/theorems already known to them, when a glance at a captioned figure is often enough.

All in all, this is a highly recommended book on graphs, specially for those who are interested in actually implementing the algorithms.

Celina Miraglia Herrera de Figueiredo is a professor at the Systems Engineering and Computer Science Program of COPPE at the Federal University of Rio de Janeiro. Her main interests are analysis of algorithms and problem complexity, graph theory, and perfect graphs.

Vinícius Gusmão Pereira de Sá is a professor at the Department of Computer Science at the Federal University of Rio de Janeiro. His main interests are computer programming, analysis of algorithms, graph theory and combinatorics in general.

BLL — The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

Comments

Submit your Review