You are here

Combinatorial Optimization: Networks and Matroids

Eugene Lawler
Dover Publications
Publication Date: 
Number of Pages: 
BLL Rating: 

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

[Reviewed by
Brian Borchers
, on

This is a Dover reprint of a classic textbook originally published in 1976. The book concerns itself with polynomial time algorithms for optimization problems on networks and matroids.

The first six chapters of the book discuss algorithms for optimization on graphs, including shortest paths, minimum cost network flows, matching in bipartite graphs and matching in non-bipartite graphs. The second half of the book introduces the reader to matroids and algorithms for optimization problems on matroids including matroid intersection and the matroid parity problem.

The algorithms in this book are still of interest 40 years after the first publication of this book. Lawler’s presentation of the material and his examples and exercises are very clear. The fields of combinatorial optimization and computational complexity have advanced considerably since the 1970s, however, so this book can no longer be recommended as an up-to-date source on these subjects. Nevertheless, this book is of more than historical interest because of its clear presentation and outstanding exercises.

Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.

The table of contents is not available.