Cohesive subgraph computation over large sparse graphs. Algorithms, data structures, and programming techniques (Q1755625)

This thin book of 107 pages stands somewhere between an extended survey article and a tutorial. This makes it a good candidate as a basis for a course on graph analysis specialized to analyzing dense subgraphs. The choice of topics is geared towards variants of the problem that can be solved efficiently, i.e., for computationally hard problems, approximation algorithms are considered. After an introduction in Chapter 1, Chapters 2 and 3 make a gentle start by introducing the simple yet useful and efficiently computable framework of core-decompositions that can infer all subgraphs of minimum degree $k$ for all values of $k$ together in linear time. The book goes into a lot of detail here including guidelines on the implementation. The subsequent chapters introduce generalizations based on average degree (Chapter 4), enumeration of triangles and $k$-cliques (Chapter 5), and decomposition based on edge connectivity (Chapter 6). \par To better fill the targeted role as an extended survey, a more detailed review of advanced results and more difficult problems might have been useful. For the role as a tutorial, it would have been nice to also discuss widely used graph analysis frameworks such as NetworKit or graphtool and how to use them in a course.