An efficient algorithm to solve the distance k-domination problem on permutation graphs. (3rd March 2016) - Rana, Akul; Pal, Anita; Pal, Madhumangal
Abstract: Let G = (V, E) be a graph and k be a fixed positive integer. A distance k -dominating set in a graph G, is a set of vertices D in V such that every vertex in V\D is at distance at most k from some vertex in D. The minimum cardinality distance k -dominating set in G is the distance k -domination number γk. The distance k -domination problem is to find a γk in G. This problem generalizes the dominating set problem, a central problem in theoretical computer science and is therefore NP-complete for general graphs. The main result of this paper is a better time bound for distance k -domination on permutation graphs by exploiting the structure of permutation in a direct way.