Polynomial time algorithm for k-vertex-edge dominating problem in interval graphs

Let G be a connected interval graph with n vertices and m edges. For any positive integer k and any subset S of E(G), we design an O(k|S| + m) time algorithm to find a minimum k-vertex-edge dominating set of G with respect to S. This shows that the vertex-edge domination problem and the double vertex-edge domination problem can be solved in linear time. Furthermore, the k-vertex-edge domination problem can also be solved in O(km) time algorithm in interval graphs. Finally, we present a linear time algorithm to solve the independent vertex-edge domination problem for unit interval graphs.