Liar’s dominating set problem on unit disk graphs

Autor: Gautam K. Das, Ramesh K. Jallu
Rok vydání: 2020
Předmět:
Zdroj: Discrete Applied Mathematics. 286:91-99
ISSN: 0166-218X
Popis: In this paper, we consider Euclidean versions of the 2-tuple dominating set problem and the liar’s dominating set problem. For a given set P = { p 1 , p 2 , … , p n } of n points in R 2 , the objective of the Euclidean 2-tuple dominating set problem is to find a minimum size set D ⊆ P such that | N [ p i ] ∩ D | ≥ 2 for each p i ∈ P , where N [ p i ] = { p j ∈ P ∣ δ ( p i , p j ) ≤ 1 } and δ ( p i , p j ) is the Euclidean distance between p i and p j . The objective of the Euclidean liar’s dominating set problem is to find a set D ( ⊆ P ) of minimum size satisfying the following two conditions: (i) D is a 2-tuple dominating set of P , and (ii) for every distinct pair of points p i and p j in P , | ( N [ p i ] ∪ N [ p j ] ) ∩ D | ≥ 3 . We first propose a simple O ( n log n ) time 63 2 -factor approximation algorithm for the Euclidean liar’s dominating set problem. Next, we propose approximation algorithms to improve the approximation factor to 732 α for 3 ≤ α ≤ 183 , and 846 α for 3 ≤ α ≤ 282 . The running time of both the algorithms is O ( n α + 1 Δ ) , where Δ = max { | N [ p ] | : p ∈ P } . Finally, we propose a PTAS for the Euclidean 2-tuple dominating set problem.
Databáze: OpenAIRE