Graphs, networks and algorithms (Q883709)

The first English edition of this book, in 1998 (see Zbl 0931.05001), was based on a translation of the third edition of the author's German text [Graphen, Netzwerke und Algorithmen (1987; Zbl 0644.05001)]. The second edition in 2005 (see Zbl 1061.05001) added material on the network simplex method and the five-colour theorem. The third edition of this standard textbook contains further new material on graphical codes and their decoding, and many additional exercises. Recent developments for the travelling salesman problem are presented as well. At the same time, the presentation has been updated and minor corrections have been carried out. The chapters cover basic graph theory, algorithms and complexity, shortest paths, spanning trees, the greedy algorithm, flows, combinatorial applications, connectivity and depth first search, colorings, circulations, the network simplex method, the synthesis of networks, matchings, and the travelling salesman problem. The three appendices include a list of some related NP-complete problems, solutions for most of the chapter exercises, and a list of symbols used in the text. The book provides a comprehensive list of references. Appendix B, containing sample solutions for exercises, is of particular value. The solutions are concise and elegant, and integrate well with the presentation. The writing is clear and precise. The underlying mathematics is treated carefully, and developed well. The focus on algorithmic issues motivates challenging questions, and connects the presentation to many real applications. These make the text appropriate for computer science and engineering students, in addition to students of mathematics. The diversity of applications represented is a real strength of the text. While the author has more than adequately treated the conventional applications of graph-theoretic algorithms in networks, the topics treated are much broader. This in turn provides connections to other areas of mathematics, and applications, that serve to motivate students. The book is highly recommended.