Liar’s dominating set problem on unit disk graphs
| Autor: | Gautam K. Das, Ramesh K. Jallu |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Applied Mathematics
0211 other engineering and technologies Approximation algorithm 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Unit disk Running time Combinatorics Euclidean distance Set (abstract data type) 010201 computation theory & mathematics Dominating set Euclidean geometry Discrete Mathematics and Combinatorics Time complexity Mathematics |
| 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 |
| Externí odkaz: |
|
Full Text from ScienceDirect