Keywords and phrases: multiple intruder locating domination, APX-completeness, fixed parameter tractable.
Received: September 20, 2023; Accepted: December 21, 2023; Published: January 12, 2024
How to cite this article: K. A. Vidya and K. Venugopal, On approximation of multiple intruder locating domination number of a graph, Advances and Applications in Discrete Mathematics 41(1) (2024), 77-96. http://dx.doi.org/10.17654/0974165824005
This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License
References: [1] 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. [2] Maw-Shang Chang, Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput. 27(6) (1998), 1671-1694. [3] 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. [4] E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks 7(3) (1977), 247-261. [5] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms, Volume 4, Springer, 2015. [6] R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness, Congr. Numer. 87 (1992), 161-178. [7] R. G. Downey and M. R. Fellows, Fundamentals of parameterized complexity, Texts in Computer Science, Springer, London, 2013. [8] P. Flach and L. Volkmann, Estimations for the domination number of a graph, Discrete Math. 80(2) (1990), 145-151. [9] J. Flum and M. Grohe, Parameterized complexity theory (Texts in Theoretical Computer Science, An EATCS Series), Springer-Verlag, Berlin, Heidelberg, 2006. [10] 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. [11] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, CRC Press, 1998. [12] C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci. 43(3) (1991), 425 440. [13] L. A. Sanchis, Maximum number of edges in connected graphs with a given domination number, Discrete Math. 87(1) (1991), 65-72. [14] 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. [15] 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. [16] K. Venugopal and K. A. Vidya, Multiple intruder locating domination in infinite grids, Advances and Applications in Discrete Mathematics 24(1) (2020), 1-12. [17] 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.
|