%0 Journal Article
%T Efficient Algorithms to Solve k-Domination Problem on Permutation Graphs
%A Akul Rana
%A Anita Pal
%A Madhumangal Pal
%J Advances in Mathematical and Computational Methods
%D 2012
%I 
%R 10.5729
%X 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.
%K Design of algorithms
%K Analysis of algorithms
%K Permutation graph
%K K-domination
%K Total k-domination
%U http://www.ier-institute.org/2160-0635/v2/no3/045.pdf