You are here

Graph Algorithms

Shimon Even
Publisher: 
Cambridge University Press
Publication Date: 
2011
Number of Pages: 
189
Format: 
Paperback
Edition: 
2
Price: 
32.99
ISBN: 
9780521736534
Category: 
Textbook
[Reviewed by
Miklós Bóna
, on
12/4/2011
]

This reviewer was skeptical when he saw the rather general title of the book, but his skepticism proved to be unfounded. The book indeed does what its title promises: it covers basic algorithms on graphs starting from the very first chapter.

Previous knowledge of graphs is not necessary. The author covers as much graph theory as any one-semester combinatorics textbook, but each chapter has an strong algorithmic component. The list of discussed algorithms is not overly surprising; we find everything we expected (spanning trees, shortest path, depth-first-search, the Ford-Fulkerson algorithm), and a little bit more (testing planarity, uniquely decipherable codes).

The reviewer has two critical remarks. One is that none of the exercises in the book come with any kind of answers, which may make self-study difficult. This leads to the second issue, namely that if the book is not intended for self-study, then what is it intended for? At only eight chapters and less than 190 pages, it seems way too short for a full-semester 3-credit course. That is unfortunate, because otherwise the book does fill an existing gap in that it teaches graph algorithms to students who may not even have known graphs beforehand.


Miklós Bóna is Professor of Mathematics at the University of Florida.

1. Paths in graphs
2. Trees
3. Depth-first search
4. Ordered trees
5. Flow in networks
6. Applications of network flow techniques
7. Planar graphs
8. Testing graph planarity.