Minimum 2-Tuple Dominating Set of an Interval Graph. (26th December 2011)

• Record Type: Journal Article
• Authors: Pramanik, Tarasankar; Mondal, Sukumar; Pal, Madhumangal
• Other Names: Hattingh Johannes Academic Editor.
• Is Part Of: International journal of combinatorics. Volume 2011(2011)
• Publication Date: 2011-12-26
• Subjects: Combinatorial analysis -- Periodicals; Combinatorial analysis; Periodicals; Electronic journals; 511.605
• DOI: 10.1155/2011/389369
• Languages: English
• ISSNs: 1687-9163

Abstract

Abstract : Thek -tuple domination problem, for a fixed positive integerk, is to find a minimum size vertex subset such that every vertex in the graph is dominated by at leastk vertices in this set. The case whenk = 2 is called 2-tuple domination problem or double domination problem. In this paper, the 2-tuple domination problem is studied on interval graphs from an algorithmic point of view, which takesO ( n 2 ) time, n is the total number of vertices of the interval graph.