Efficient Algorithms to Solve k-Domination Problem on Permutation Graphs

A set D of vertices in a connected graph G = (V,E) is a kdominating set of G if every vertex of G is at distance k or less from some vertex in D. D is a total k-dominating set of G if the subgraph induced by D in G has no isolated vertex. Let G be a permutation graph. In this paper, we present two algorithms with time complexity O(n + m). The first algorithm is designed for finding a minimum cardinality kdominating set and other for finding a minimum cardinality total kdominating set in a permutation graph G, where m is the number of edges in G, the complement graph. The dynamic programming approach is used to solve the problem.