No label defined (Q4378629)

In a given undirected graph \(G= (V, E)\), a vertex set \(U\subseteq V\) is called dominating if every vertex outside \(U\) has a neighbour in \(U\). The domination problem is to find a minimum (weight) dominating set in a given graph. Domination is one of the most-investigated algorithmic problems on graphs. It comes in many variants, and there are many papers studying the computational complexity of this problem and its variants on special classes of graphs. Dieter Kratsch has written a very useful survey which can serve as a guide to the many results. I used it already several times in order to compare new results of authors with existing ones, and in some cases it turned out that the informations in Dieter's survey were more complete than those given in the new research papers. The chapter on domination algorithms is not only giving a bibliography but is also demonstrating some basic techniques for the design of efficient domination algorithms on some special graph classes. For the entire collection see [Zbl 0883.00011].