Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Guide to graph algorithms : sequential, parallel and distributed
Erciyes K., Springer International Publishing, New York, NY, 2018. 471 pp. Type: Book (978-3-319732-34-3)
Date Reviewed: Jan 22 2019

This comprehensive text focuses on graph data structures and consequent graph algorithms as fundamental to the analysis of various types of networks, from social to biological ones. The book consists of three parts, with 15 chapters including an epilogue. The text is easy to read and includes complementary pseudocode.

Part 1 (chapters 1 to 5) provides the fundamentals of graph structures and algorithms. This part is large; however, it is also unfocused since the author tries to incorporate or at least mention all major topics in parallel programming. As such, the whole of chapters 1 and 2 give basic undergraduate-level material such as types of graph algorithms, types of graphs, graph representations, and relationships between matrices and graphs. Further chapters--for example, chapter 4--provide brief introductions to parallel programming, including message passing interface (MPI) and thread examples. The latter is too shallow, however, and the introductory-level “MPI as six instructions” format, while easy to understand, is barely enough for serious programming implementations. In addition, all algorithms are presented in pseudocode. The same is true for topics such as processor allocation and dynamic load balancing, which are just illustrated. Nevertheless, the text in Part 1 is well structured and the style is light, so interested readers may easily skip the sections that have only illustrative value.

Part 2, the core of the book, covers chapters 6 to 11. Readers will find systematic and detailed analyses of sequential parallel and distributed algorithms for fundamental graph problems such as trees, breadth-first search (BFS), and depth-first search (DFS). Weighted graphs are also presented, along with sequential and parallel versions of classical algorithms (Boruvka, Kruskal, Prim, and so on).

In the third part, “Advanced Topics,” readers can find discussions of dynamic and algebraic graph algorithms. Large graphs are also discussed in detail, in chapter 13. A significant plus of the book is its discussions of complex networks (chapter 14) and real-life instances and biological, social, and information networks.

Overall, this good book is well suited for advanced undergraduates and may serve as a starting point for graduate students.

Reviewer:  Alexander Tzanov Review #: CR146392 (1904-0094)
Bookmark and Share
  Reviewer Selected
Editor Recommended
Featured Reviewer
 
 
Graph Algorithms (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Algorithms": Date
Planar graph decomposition and all pairs shortest paths
Frederickson G. (ed) Journal of the ACM 38(1): 162-204, 1991. Type: Article
Oct 1 1991
High probability parallel transitive-closure algorithms
Ullman J., Yannakakis M. SIAM Journal on Computing 20(1): 100-125, 1991. Type: Article
Dec 1 1991
Clique partitions, graph compression and speeding-up algorithms
Feder T., Motwani R.  Theory of computing (, New Orleans, LA, May 6-8, 1991)1331991. Type: Proceedings
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy