.svg){kind=logo}
ON APPROXIMATION OF MULTIPLE INTRUDER LOCATING DOMINATION NUMBER OF A GRAPH
Keywords:
multiple intruder locating domination, APX-completeness, fixed parameter tractable.DOI:
https://doi.org/10.17654/0974165824005Abstract
Let $G=(V, E)$ be a graph and $S \subseteq V$. Then a vertex $c$ of $G$ is called a codeword if $c \in S$, otherwise $c$ is called a non-codeword. The set $S$ is called a Multiple Intruder Locating Dominating (MILD) set if every non-codeword $v$ is adjacent to a codeword $c$ which is not adjacent to any other non-codeword other than $v$. The cardinal of a minimum MILD set of graph $G$ is called its MILD number, denoted by $\gamma_{m l}(G)$.
The problem of finding the MILD number of a graph is known to be NP-complete for arbitrary graphs. In this paper, we present a simple approximation algorithm to find the MILD number of an arbitrary graph. We then consider the question of whether a polynomial time approximation scheme can be devised for the problem in bipartite and chordal graphs. Finally, the parameterized complexity of the MILD problem is discussed.
Received: September 20, 2023
Accepted: December 21, 2023
References
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties, U.S. Government Printing Office, 1999.
Maw-Shang Chang, Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput. 27(6) (1998), 1671-1694.
E. Cockayne, S. Goodman and S. Hedetniemi, A linear algorithm for the domination number of a tree, Inform. Process. Lett. 4(2) (1975), 41-44.
E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks 7(3) (1977), 247-261.
M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms, Volume 4, Springer, 2015.
R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness, Congr. Numer. 87 (1992), 161-178.
R. G. Downey and M. R. Fellows, Fundamentals of parameterized complexity, Texts in Computer Science, Springer, London, 2013.
P. Flach and L. Volkmann, Estimations for the domination number of a graph, Discrete Math. 80(2) (1990), 145-151.
J. Flum and M. Grohe, Parameterized complexity theory (Texts in Theoretical Computer Science, An EATCS Series), Springer-Verlag, Berlin, Heidelberg, 2006.
T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in graphs: advanced topics, Monographs and Textbooks in Pure and Applied Mathematics 209, 1998.
T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, CRC Press, 1998.
C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci. 43(3) (1991), 425 440.
L. A. Sanchis, Maximum number of edges in connected graphs with a given domination number, Discrete Math. 87(1) (1991), 65-72.
K. Venugopal and K. A. Vidya, Multiple intruder locating dominating sets, International Journal of Scientific Research in Mathematical and Statistical Sciences 6(2) (2019), 394-398.
K. Venugopal and K. A. Vidya, Multiple intruder locating dominating sets in graphs: an algorithmic approach, Communications in Mathematics and Applications 11(2) (2020), 259-269.
K. Venugopal and K. A. Vidya, Multiple intruder locating domination in infinite grids, Advances and Applications in Discrete Mathematics 24(1) (2020), 1-12.
K. Venugopal and K. A. Vidya, Multiple intruder locating domination in chordal and bipartite graphs, Advances and Applications in Mathematical Sciences 21(10) (2022), 5731-5742.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA
This work is licensed under a Creative Commons Attribution 4.0 International License.
_________________________
Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.
Contact Pushpa Publishing House for more info or permissions.
Journal Impact Factor: 
