Graphs, networks and algorithms. (Q455381): Difference between revisions

This book is the fourth edition of a popular textbook that first came out a quarter of century ago. It contains an abundant amount of material in the area of graph related combinatorial optimization problems. After a preparatory (p)review on graph theory with many stimulating exercises and a detailed example centered on factorizations, and a practical introduction to algorithms and a rather concise characterization of their complexity and NP-completeness related issues, this book presents a whole collection of classical and well motivated real-life problems such as shortest path construction, spanning tree identification, greedy algorithms, network flow problems, Menger's theorem, its company and their application in solving some combinatorial problems, various graph search problems, graph coloring, and circulation problems. It is clear that the author is much more interested in constructing solutions for real problems, besides proving existence of various properties related to them. Take the shortest path chapter as an example. After defining the problem, the author first discusses the metric space of distances and then applies it to construct the Breadth First Search algorithm and characterizes bipartite graphs. Assuming a graph does not contain a negative cycle, the author brings us to the concept of shortest path trees, and then a linear shortest path construction algorithm for acyclic graph, based on Bellman's equations, which is followed by an application on longest path construction in the context of project scheduling. The author then introduces the classic Dijkstra algorithm when the lengths of all the edges are non-negative, followed by another application in train scheduling. By weakening the edge negativity restriction, the author sets the stage for the Floyd and Warshall algorithm, which also addresses the issue of identifying the existence of negative cycles in a network. Finally, the author treats us with a solution of the above Bellman's equations in terms of linear algebra. Many examples, exercises and well cited references spread all over the chapter. I believe this is as full and deep a coverage as one can get on this topic. This book also explores some of the essential tools in this area such as the Network simplex algorithm, including its general structure and an efficient implementation. The main course of this book ends with a rather detailed exposition of the famously hard traveling salesman problem, where many techniques and heuristics associated with finding an approximation solution for an NP-complete problem are presented, analyzed and discussed. Almost like a dessert, this book concludes with a short list of about forty NP-complete problems, together with reference to their respective context within this monograph. It is often hard to make a choice among lots of theoretical and algorithmic issues when covering this field. This book stands out among its peers with its balanced but focused approach. It made its choice. For example, efforts are made in analyzing algorithms, but clearly it is not the focus which is understandable considering its problem solving nature. I also like the practice of including exercises, some with hints, within the text, but not at the end of chapters or sections, so that students can test her understanding of the material in a context sensitive manner. (Solutions to some of these exercises are provided at the end of the book.) Numerous background notes with citation rightly place the issues into their context, thanks to a comprehensive list of references, perhaps close to a thousand items. This is certainly an accessible, serious, and time tested textbook at the graduate level on graph algorithms. I would also wholeheartedly recommend this book for professionals who work in this area as a reference book because of its thorough and encyclopedic nature. In my opinion, it is also an excellent ``introductory'' book for someone with a solid mathematical and algorithmic background who is interested in this area, as this book gives a good presentation of some of the typical problems in the area, an insightful exposition of the related theoretical issues, as well as the associated classic algorithmic solutions with sufficient analysis.