Minimum 2-Tuple Dominating Set of an Interval Graph

الملخص EN

The k-tuple domination problem, for a fixed positive integer k, is to find a minimum size vertex subset such that every vertex in the graph is dominated by at least k vertices in this set.

The case when k=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 takes O(n2) time, n is the total number of vertices of the interval graph.