An efficient algorithm to solve the distance k-domination problem on permutation graphs. (3rd March 2016)

• Record Type: Journal Article
• Authors: Rana, Akul; Pal, Anita; Pal, Madhumangal
• Is Part Of: Journal of discrete mathematical sciences & cryptography. Volume 19:Number 2(2016)
• Page Start: 241
• Page End: 255
• Publication Date: 2016-03-03
• Subjects: Design of algorithms -- analysis of algorithms -- permutation graph -- k-domination -- caterpillar; Computer science -- Mathematics -- Periodicals; Cryptography -- Periodicals; Computer science -- Mathematics; Cryptography; Periodicals; 004.0151
• DOI: 10.1080/09720529.2014.986906
• Languages: English
• ISSNs: 0972-0529

Abstract

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.