Connected liar's domination in graphs: complexity and algorithm

摘要

A subset L V of a graph G = (V;E) is called a connectedliar's dominating set of G if (i)jN[v] Lj 2 for every vertex v 2V ,(ii)j(N[v][N[u])Lj 3 for every pair of distinct vertices u; v 2 V ,and (iii) the induced subgraph of subset L is connected. In this paper,we show another proof of the minimum connected liar's dominating setproblem is NP-hard, and present a 2(1+ln )-approximation algorithmof minimum connected liar's dominating set in general graph.