PTASs for secure dominating set in planar graphs and growth-bounded graphs.

Given a graph G with vertex set V and edge set E , a vertex set D is a dominating set (DS) of G , if every vertex v ∈ V is either in D or adjacent to a vertex in D. If D is a DS of G and for every vertex v ∈ V ∖ D there exists a vertex u ∈ D adjacent to v such that (D ∖ { u }) ∪ { v } is also a DS of G , then D is a secure dominating set (SDS). The minimum secure dominating set problem (MinSDS) is to find an SDS of G with the minimum cardinality. In this paper, we design PTASs for MinSDS on planar graphs and growth-bounded graphs, that is, the computed solutions approximate the optimal value within factor (1 + ɛ) for any constant ɛ ∈ (0 , 1). [ABSTRACT FROM AUTHOR]