Connected dominating set. Theory and applications (Q436191): Difference between revisions

A set \(S\) of vertices in a graph \(G\) is a dominating set if its closed neighborhood (all vertices either in \(S\) or adjacent to a vertex in \(S\)) is the whole vertex set of the graph. Within the already large area of domination in graphs, the book under review covers the specific topic of connected dominating sets, namely, dominating sets which induce a connected subgraph of \(G\). The authors give a clear motivation for the topic from problems on wireless, optical and sensor networks. The book focuses on the algorithmic aspects of finding small connected dominating sets or a large number of disjoint connected dominating sets. Both problems are algorithmically hard, and the goal is to find approximation algorithms and to consider particular classes of graphs. After an introduction to the general topic, the second chapter deals with approximation algorithms for general graphs, with a discussion on optimization of submodular functions adapted to the connected dominating sets problem. The rest of the book is organized in 11 additional chapters which mainly focus on graphs with geometric flavour: unit disk graphs, unit ball graphs, disk containment graphs, disk intersection graphs and planar graphs. Constrained, directed and weighted versions of the problem are also considered. Every chapter contains an opening section which motivates the choice of the setting and the problems to be considered, often including some open problems. There are full proofs of all needed results, including for instance the Zassenhaus-Groemer-Oler inequality on the largest number of unit discs contained in a compact convex region in the plane, or the solution by Hoppe of the Newton-Gregory problem on the kissing number of spheres in 3-dimensional space. The book surveys the research within the scope set by the authors in the last 15 years. The writing is quite basic and the glossary is rather poor, but the book is well organized and brings interesting topics and mathematical discussions.