کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435955 | 689955 | 2015 | 17 صفحه PDF | دانلود رایگان |
A subset L⊆VL⊆V of a graph G=(V,E)G=(V,E) is called a liar's dominating set of G if (i) |NG[u]∩L|≥2|NG[u]∩L|≥2 for every vertex u∈Vu∈V, and (ii) |(NG[u]∪NG[v])∩L|≥3|(NG[u]∪NG[v])∩L|≥3 for every pair of distinct vertices u,v∈Vu,v∈V. The Min Liar Dom Set problem is to find a liar's dominating set of minimum cardinality of a given graph G and the Decide Liar Dom Set problem is the decision version of the Min Liar Dom Set problem. The Decide Liar Dom Set problem is known to be NP-complete for general graphs. In this paper, we first present approximation algorithms and hardness of approximation results of the Min Liar Dom Set problem in general graphs, bounded degree graphs, and p-claw free graphs. We then show that the Decide Liar Dom Set problem is NP-complete for doubly chordal graphs and propose a linear time algorithm for computing a minimum liar's dominating set in block graphs.
Journal: Theoretical Computer Science - Volume 573, 30 March 2015, Pages 26–42