Algorithmic studies on graph domination -refinements and extensions

Abstract

Given a graph G = (V, E), where V is a finite set of vertices and E is the set of edges, a set D ? V of vertices is a dominating set if every vertex in V ? D is adjacent to some vertex in D. The size of a minimum cardinality dominating set is the domination number. The domination problem, or the problem of finding a minimum cardinality dominating set, is of interest both in algorithm design and in complexity theory. This problem, though not as widely studied as the independent set, clique, and coloring problems, is now rapidly gaining interest among researchers. The domination problem has applications in facility location, coding theory, and combinatorial optimization. This work concerns the study and design of algorithms for the domination problem and its variants on certain classes of graphs. We give some extensions and modifications of existing algorithms and present new algorithms. We provide simple extensions of existing algorithms in the case of 'almost' trees and k-trees. For the class of permutation graphs, we develop a simple O(n) time algorithm based on the notion of a geometric representation. The most efficient existing algorithms, in this case, are of complexity O(n²). For the class of directed path graphs, we give linear time algorithms using a single general technique.