Graphs, networks and algorithms.

DOI10.1007/978-3-642-32278-5MaRDI QIDQ455381zbMATH OpenOpenAlexFDO

Publication date 5 October 2012

Published in Algorithms and Computation in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32278-5

approximation algorithms combinatorics complexity graph theory optimization algorithms

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Graph theory (05Cxx) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68Wxx)

Review text

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.

Recommendations

Cited in

(37)

This page was built for publication: Graphs, networks and algorithms.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q455381)