scientific article; zbMATH DE number 1124601
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].
- Algorithms in SINGULAR
- Algorithms for dominating clique problems
- On dominating sets whose induced subgraphs have a bounded diameter
- An exact algorithm for the minimum dominating clique problem
- Improved bottleneck domination algorithms
- D E K=(100)_8
- scientific article; zbMATH DE number 3918387 (Why is no real title available?)
- scientific article; zbMATH DE number 1302196 (Why is no real title available?)
- scientific article; zbMATH DE number 194559 (Why is no real title available?)
- scientific article; zbMATH DE number 7434637 (Why is no real title available?)
- Algorithms on Graphs with Small Dominating Targets
- scientific article; zbMATH DE number 958772 (Why is no real title available?)
- scientific article; zbMATH DE number 2222002 (Why is no real title available?)
- A survey on variant domination problems in geometric intersection graphs
- Improved algorithms and complexity results for power domination in graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4378629)