Number of the records: 1
Liar's Domination in 2D
- 1.
SYSNO ASEP 0534918 Document Type C - Proceedings Paper (int. conf.) R&D Document Type The record was not marked in the RIV Title Liar's Domination in 2D Author(s) Jallu, Ramesh Kumar (UIVT-O) RID, ORCID, SAI
Das, G. K. (IN)Number of authors 2 Source Title Algorithms and Discrete Applied Mathematics. - Cham : Springer, 2017 / Narayanaswamy N.S. ; Gaur D - ISSN 0302-9743 - ISBN 978-3-319-53006-2 Pages s. 219-229 Action CALDAM 2017. International Conference /3./ Event date 16.02.2017 - 18.02.2017 VEvent location Sancoale, Goa Country IN - India Event type WRD Language eng - English Country CH - Switzerland Keywords graphs ; approximation ; algorithms ; Unit disk graph ; Approximation algorithm ; Dominating set ; Liar's dominating set UT WOS 000418573900020 EID SCOPUS 85012260225 DOI 10.1007/978-3-319-53007-9_20 Annotation In this paper we consider Euclidean liar's domination problem, a variant of dominating set problem. In the Euclidean liar's domination problem, a set P = {p(1), p(2),..., p(n)} of n points are given in the Euclidean plane. For p is an element of P, N[p] is a subset of P such that for any q is an element of N[p], the Euclidean distance between p and q is less than or equal to 1. The objective of the Euclidean liar's domination problem is to find a subset D(. P) of minimum size having the following properties: (i) |N[p(i)] boolean AND D| >= 2 for 1 <= i <= n, and (ii) |(N[p(i)]boolean OR N[p(j)]) n D| = 3 for i not equal j, 1 <= i, j <= n. We first propose a simple O(n log n) time 63/2-factor approximation algorithm for the liar's domination problem. Next we propose approximation algorithms to improve the approximation factor to 732 k for 3 <= k <= 183, and 846/k for 3 <= k <= 282. The running time of the algorithms is O(n(k+1) Delta), where Delta = max{|N[p]| : p is an element of P}. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2021
Number of the records: 1