chapter  12
28 Pages

Domination Complexity and Algorithms

With more than 200 research papers published on the algorithmic complexity of domination and related parameters of graphs, it is difficult to know what to cover in a relatively short chapter on the subject, especially since it could take quite a few pages just to cover the preliminaries of computational complexity and the many algorithm design paradigms that have been applied to domination problems. But consider this. It is well known and generally accepted that the problem of determining the domination number of an arbitrary graph is a difficult one. Since this problem has been shown to be NP-complete (see Chapter 1), it is generally thought to require exponential t ime in the order of the graph. Because of this, researchers have turned their attention to the study of classes of graphs for which the domination problem can be solved in polynomial time.