Guide to graph algorithms. Sequential, parallel and distributed (Q1753241)

Besides the Introduction (Chapter 1), the book is divided into three parts. The first part consists of four chapters that introduce graphs and graphs algorithms. Chapter 2 discusses the foundations of graph theory, including basic graph theoretical definitions, graph operations, types of graphs and graph representations. Chapter 3 (slightly misleadingly entitled ``Graphs Algorithms'') introduces a sequential algorithm, its asymptotic analysis and gives a short survey on NP-completeness and some algorithm design methods. The topic of algorithms is carried on in Chapters 4 and 5 where parallel graph algorithms and distributed graph algorithms are introduced. It is worth mentioning that, in the context of this book, distributed graph algorithms are the algorithms running in a network represented by a graph. The second part of the book presents basic graph algorithms. Each chapter of this part addresses a graph-theoretical topic and the algorithms which solve the topic-related problems using all three paradigms: sequential, parallel and distributed. For a given problem, a comprehensive list of sequential algorithms is typically provided, while only some instances of parallel and distributed algorithms are given. For example, the first chapter of this part (Chapter 6) considers the trees and graphs traversals. The chapter provides several algorithms on trees, including binary trees and heaps as their special example, as well as DFS and BFS graph traversing algorithms. In the frame of the distributed paradigm, the chapter reviews a synchronous and an unsynchronous BFS algorithm as well as a basic distributed DFS algorithm, while, on the other hand, it discusses only outlines of the parallel DFS and BFS approaches. The other graph-theoretical topics included in this part of the book (Chapters 7--11) are weighted graphs, connectivity of graphs, matchings, independent sets, domination sets, vertex covers and vertex and edge colorings. The third part of the book discusses some more advanced topics in graph algorithms. Chapter 12 is devoted to algorithms that employ matrices commonly associated to a graph (called algebraic graph algorithms) and the algorithms on graphs which are subject to update operations (called dynamic graph algorithms). Chapter 13 discusses algorithms for the analysis of large graphs which require novel graph invariants and adapted algorithmic approaches. The presented topic is to a certain extent continued in Chapter 14 where complex networks (e.g. biological, social, technological or information networks) are reviewed. Since the intended audience for this book is the senior/graduate students of non-mathematical studies (this book is a part of Springer's `Texts in Computer Science' series), its theoretical content is relatively comprehensive. Nevertheless, the graph theoretical part is the weakest point of the book. In certain cases, the book is inconsistent and not mathematically rigorous. Even the main subject of the book, the notion of a graph, is vaguely introduced. Namely, in the Introduction (page 1), the author says: ``A graph is shown as \(G=(V,E)\) where \(V\) is the set of vertices and \(E\) is the set of edges it has'' (no explanation about the set of edges is given). On page 16 it is stated that ``A graph is a set of points and set of lines in a plane or a 3-D space'' and immediately after that (Definition 2.1): ``A graph \(G=(V,E,g)\) or \(G=(V(G), E(G), g)\) is a discrete structure consisting of a vertex set \(V\) and an edge set \(E\) and a relation \(g\) that associates each edge with two vertices of the set \(V\).'' The above comment does not intend to doubt the overall merit of the book. I find the book well devised, the idea of combining three paradigms is inventive and gives the reader the opportunity to view the solutions of the problem from various perspectives. The aim of my remark is to give suggestions for improvements concerning future editions. In particular, a careful review by a graph theory specialist would significantly improve the quality of the book.