Minimum 2-tuple dominating set of an interval graph (Q666518)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum 2-tuple dominating set of an interval graph |
scientific article |
Statements
Minimum 2-tuple dominating set of an interval graph (English)
0 references
8 March 2012
0 references
Summary: 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(n^2)\) time, \(n\) is the total number of vertices of the interval graph.
0 references
intersection graph
0 references
dominating set
0 references