- Tytuł:
- The Complexity of Secure Domination Problem in Graphs
- Autorzy:
-
Wang, Haichao
Zhao, Yancai
Deng, Yunping - Powiązania:
- https://bibliotekanauki.pl/articles/31342335.pdf
- Data publikacji:
- 2018-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
secure domination
star convex bipartite graph
doubly chordal graph
NP-complete
APX-complete - Opis:
- A dominating set of a graph G is a subset D ⊆ V (G) such that every vertex not in D is adjacent to at least one vertex in D. A dominating set S of G is called a secure dominating set if each vertex u ∈ V (G) \ S has one neighbor v in S such that (S \ {v}) ∪ {u} is a dominating set of G. The secure domination problem is to determine a minimum secure dominating set of G. In this paper, we first show that the decision version of the secure domination problem is NP-complete for star convex bipartite graphs and doubly chordal graphs. We also prove that the secure domination problem cannot be approximated within a factor of (1−ε) ln |V | for any ε > 0, unless NP⊆DTIME (|V |O(log log |V|)). Finally, we show that the secure domination problem is APX-complete for bounded degree graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 385-396
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł