The very successful first edition of this book was a translation of a revised version of the third edition of the author’s German text book Graphen, Netzwerke und Algorithmen. In this substantially revised second edition, the author has added a chapter on the network simplex algorithm and a section on the five color theorem (including a short history of the four color theorem), as well as making numerous small changes and corrections, and reporting on recent related developments. The remaining 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 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 rounds out with a comprehensive list of references.
The substantial development effort of this text, involving multiple editions and trialling in the context of various workshops, university courses and seminar series, clearly shows through in this new edition with its clear writing, good organisation, comprehensive coverage of essential theory, and well-chosen applications. The proofs of important results and the representation of key algorithms in a Pascal-like notation allow this book to be used in a high-level undergraduate or low-level graduate course on graph theory, combinatorial optimization or computer science algorithms. The well-worked solutions to exercises are a real bonus for self study by students. The book is highly recommended.