Skip to main navigation menu Skip to main content Skip to site footer

Vol. 46 No. 1 (2020)
Serdica Mathematical Journal

Articles

An optimal algorithm for computing minimum \(k\)-hop dominating set of permutation graphs

Published 22-06-2020

  • Sambhu Charan Barman
    • ,
  • Madhumangal Pal
    • ,
  • Sukumar Mondal

Sambhu Charan Barman
Shahid Matangini Hazra Govt. College for Women, India

Madhumangal Pal
Vidyasagar University, India

Sukumar Mondal
Raja N. L. Khan Women’s College, India

Abstract

A  \(k\)-hop dominating set (\(k\)-HDS) \(D\) of a graph \(G = (V,E)\) is a subset of \(V\) such that every vertex \(x\in V\) is within \(k\)-steps from at least one vertex \(y\in D\), i.e., \(d(x,y)\leq k\), where \(k\) is a fixed positive integer. A \(k\)-hop dominating set \(D\) is said to be minimal if there does not exist any \(H\subset D\) such that \(H\) is a \(k\)-HDS of \(G\). If a dominating set \(D\) is minimal as well as it is \(k\)-HDS then it is said to be minimum \(k\)-hop dominating set. In this paper, we present an optimal algorithm to compute a minimum \(k\)-HDS of permutation graphs with \(n\) vertices which runs in \(O(n)\) time.

2020 Mathematics Subject Classification:

05C30, 05C12, 68R10, 68Q25

Keywords

Design and analysis of algorithms, \(k\)-hop domination, permutation graphs

Full text

Author Details

Sambhu Charan Barman

Department of Mathematics
Shahid Matangini Hazra Govt. College for Women
Nimtouri, Purba Medinipur
721649 West Bengal, India
e-mail: barman.sambhu@gmail.com

Madhumangal Pal

Department of Applied Mathematics
with Oceanology and Computer Programming
Vidyasagar University
721102 Midnapore, India
e-mail: mmpalvu@gmail.com

Sukumar Mondal

Department Of Mathematics
Raja N. L. Khan Women’s College
Gope Palace
721102 Midnapore, India
e-mail: sm5971@rediffmail.com

References

  1. B. Awerbuch, D. Peleg. Sparse partitions (extended abstract). In: 31st Annual Symposium on Foundations of Computer Science, 1990, 503–513, https://doi.org/10.1109/FSCS.1990.89571.
  2. S. K. Ayyaswamy, B. Krishnakumari, C. Natarajan, Y. B. Venkatakrishnan. Bounds on the hop domination number of a tree. Proc. Indian Acad. Sci. Math. Sci. 125, 4 (2015), 449–455.
  3. S. C. Barman, M. Pal, S. Mondal. An efficient algorithm to find next-to-shortest path on permutation graphs. J. Appl. Math. Comput. 31, 1–2 (2009), 369–384.
  4. S. C. Barman, M. Pal, S. Mondal. An optimal algorithm to find minimum k-hop dominating set of interval graphs. Discrete Math. Algorithms Appl. 11, 2 (2019), 1950016, 18 pp, https://doi.org/10.1142/S1793830919500162.
  5. P. Basuchowdhuri, S. Majumder. Finding influential nodes in social networks using minimum k-hop dominating set. In: Applied Algorithms, ICAA 2014 (Eds P. Gupta, C. Zaroliagis) Lecture Notes in Computer Science, vol. 8321, Cham, Springer, https://doi.org/10.1007/978-3-319-04126-1_12.
  6. D. A. Benson, M. S. Boguski, D. J. Lipman, J. Ostell, B. F. Ouellette, B. A. Rapp, D. L. Wheeler. GenBank. Nucleic Acids Research 27, 1 (1999) 12–17, https://doi.org/10.1093/nar/27.1.10.
  7. S. Berchtold, C. Böhm, H. P. Kriegel. The pyramid-technique: Towards breaking the curse of dimensionality. In: Proc. Int. Conf. on Management of Data, ACM SIGMOD, Seattle, Washington, 1998, ACM SIGMOD Records, 27, 2 (1998), https://doi.org/10.1145/276305.276318
  8. S. Berchtold, D. Keim, H.-P. Kriegel. The X-tree: an index structure for high-dimensional data. VLDB ’96, Proceedings of the 22th International Conference on Very Large Data Bases, (Eds T. M. Vijayaraman, A. P. Buchmann) September 1996, 28–39.
  9. E. Berger. Dynamic monopolies of constant size. Technical report, Los Alamos National Laboratories, 1999, arXiv:math/9911125.
  10. A. A. Bertossi, A. Gori. Total domination and irredundance in weighted interval graphs. SIAM J. Discrete Math. 1, 3 (1988), 317–327.
  11. G. J. Chang. Algorithmic aspect of domination in graphs. In: Handbook of Combinatorial Optimization, vol. 1, (Eds P. M. Pardalos, D.-Z. Du, R. L. Graham) New York, Springer, 2013, 221–282.
  12. G. J. Chang. The weighted independent domination problem is NP-complete for chordal graphs. Discrete Appl. Math. 143, 1–3 (2004), 351–352.
  13. M. S. Chang. Weighted domination of cocomparability graphs. Discrete Appl. Math. 80, 2–3 (1997), 135–148.
  14. H. S. Chao, F. R. Hsu, R. C. T. Lee. An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs. Discrete Appl. Math. 102, 3 (2000), 159–173.
  15. C. C.-Y. Chen, S. K. Das. Breadth-first traversal of trees and integer sorting in parallel. Infom. Process. Lett. 41, 1 (1992), 39–49.
  16. T. C. E. Cheng, L. Y. Kang, E. Shan. A polynomial-time algorithm for the paired domination problem on permutation graphs. Discrete Appl. Math. 157, 2 (2009), 262–271.
  17. T. C. E. Cheng, L. Y. Kang, C. T. Ng. Paired domination on interval and circular-arc graphs. Discrete Appl. Math. 155, 16 (2007), 2077–2086.
  18. L. Chen, C. Lu., Z. Zeng. A linear time algorithm for paired-domination problems in strongly chordal graphs, Inform. Process. Lett. 110, 1 (2009), 20–23.
  19. L. Chen, C. Lu, Z. Zeng. Labelling algorithm for paired-domination problems in block and interval graphs. J. Comb. Optim. 19, 4 (2010), 457–470.
  20. E. Cockayne, R. Dawes, S. Hedetniemi. Total domination in graphs. Networks 10, 3 (1980), 211–219.
  21. E. Cockayne, S. Goodman, S. Hedetniemi. A linear algorithm for the domination number of a tree. Information Processing Lett. 4, 2 (1975), 41–44.
  22. A. D’Atri, M. Moscarini. Distance-hereditary graphs, Steiner trees, and connected domination. SIAM J. Comput. 17, 3 (1988), 521–538.
  23. C. F. De Jaenisch. Traite des Applications de l’Analyse Mathematique au Jeu des Echecs. Petrograd, 1862.
  24. E. D. Demaine, M. Hajjaghay, D. M. Thilikos. Fixed parameter algorithm for (k, r) center in planar graphs and map graphs. ACM Trans. Algorithms 1, 1 (2005), 1–16.
  25. M. Farhadi Jalalvand, N. Jafari Rad. On the complexity of k-step and k-hop dominating sets in graphs. Math. Montisnigri 40 (2017), 36–41.
  26. M. C. Golumbic. Algorithmic graph theory and perfect graphs. New York-London-Toronto, Ont., Academic Press, 1980.
  27. T. W. Haynes, S. T. Hedetniemi, P. J. Slater. Domination in Graphs: Advanced Topics. Monographs and textbooks in pure and applied mathematics, vol. 209, New York, Marcel Dekker, Inc., 1998.
  28. T. W. Haynes, S. T. Hedetniemi, P. J. Slater. Domination in Graphs: Selected Topics. New York, Marcel Dekker, Inc., 1998.
  29. T. W. Haynes, S. T. Hedetniemi, P. J. Slater. Domination in Graphs: The Theory. New York, Marcel Dekker, Inc., 1998.
  30. T. W. Haynes, S. T. Hedetniemi, P. J. Slater. Fundamentals of Domination in Graphs. Monographs and Textbooks in Pure and Applied Mathematics, vol. 208. New York, Marcel Dekker, Inc., 1998.
  31. Haynes, T. W., Mynhardt, C. M. and van der Merwe, L. C., Total domination edge critical graphs, Utilitas Math. 54 (1998) 229–240.
  32. Haynes, T. W., Mynhardt, C. M. and van der Merwe, L. C., Total domination edge critical graphs with maximum diameter, Discussiones Math. Graph Theory 21 (2001) 187–205.
  33. T. W. Haynes, P. J. Slater. Paired-domination in graphs. Networks 32, 3 (1998) 199–206.
  34. S. T. Hedetniemi, R. C. Laskar. Bibliography on domination in graphs and some basic definitions of domination parameters. Discrete Math. 86, 1–3 (1990), 257–277.
  35. S. T. Hedetniemi, R. C. Laskar. Topics on Domination. Amsterdam, North-Holland, 1991.
  36. M. A. Henning, N. Jafari Rad. On 2-step and hop dominating sets in graphs. Graphs Combin. 33, 4 (2017), 913–927, https://doi.org/10.1007/s00373-017-1789-0.
  37. R. W. Hung. Linear time algorithm for the paired-domination problem in convex bipertite graphs. Theory Comput. Syst. 50, 4 (2012), 721–738.
  38. L. Kang, M. Y. Sohn, T. C. E. Cheng. Paired-domination in inflated graphs. Theoret. Comput. Sci. 320, 2–3 (2004), 485–494.
  39. S. Kundu, S. Majumder. A linear time algorithm for optimal k-hop dominating set of a tree. Inform. Process. Lett. 116, 2 (2016), 197–202.
  40. E. Lappas, S. D. Nicolopoulos, L. Palios. An O(n)-time algorithm for the paired-domination problem on permutation graphs. Combinatorial algorithms Lecture Notes in Comput. Sci. vol. 5874, 2009, 368–379.
  41. C. S. Liao, G. J. Chang. Algorithmic aspect of k-tuple domination in graphs. Taiwanese J. Math., 6, 3 (2002) 415–420.
  42. C. S. Liao, G. J. Chang. k-tuple domination in graphs. Inform. Process. Lett., 87, 1 (2003) 45–50.
  43. C. Liu. Introduction to Combinatorial Mathematics. New York-Toronto, Ont.-London, McGraw-Hill Book Co., 1968.
  44. C. L. Lu, M.-T. Ko, C. Y. Tang. Perfect edge domination and efficient edge domination in graphs. Discrete Appl. Math. 119, 3 (2002) 227–250.
  45. J. McCoy, M. A. Henning. Locating and paired-dominating sets in graphs. Discrete Applied Math. 157, 15 (2009), 3268–3280.
  46. S. Mondal, M. Pal, T. K. Pal. An optimal algorithm to solve 2-neighbourhood covering problem on interval graphs. Int. J. Comput. Math. 79, 2 (2002), 189–204.
  47. J. H. Muller, J. Spinrad. Incremental modular decomposition. J. Assoc. Comput. Mach. 36, 1 (1989) 1–19.
  48. C. Natarajan, S. K. Ayyaswamy. Hop Domination in Graphs-II. An. Sţiinţ. Univ. “Ovidius” Constanţa Ser. Mat. 23, 2 (2015), 187–199.
  49. S. Olariu. An optimal greedy heuristic to color interval graphs. Inform. Process. Lett. 37, 1 (1991), 21–25.
  50. M. Pal, G. P. Bhattacharjee. The parallel algorithms for determining edge-packing and efficient edge dominating sets in interval graphs. Parallel Algorithms Appl. 7, 3–4 (1995), 193–207, https://doi.org/10.1080/10637199508915531.
  51. B. S. Panda, D. Pradhan. Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipertite graphs. J. Comb. Optim. 26, 4 (2013), 770–785, https://doi.org/10.1007/s10878-012-9483-x.
  52. A. Pnueli, A. Lempel, S. Even. Transitive orientation of graphs and identification of permutation graphs. Canadian J. Math., 23 (1971), 160–175.
  53. T. Pramanik, S. Mondal, M. Pal. Minimum 2-tuple dominating set of an interval graphs. Int. J. Comb. 2011 (2011), Art. ID 389369, 14 pp.
  54. H. Qiao, L. Kang, M. Gardei, D.-Z. Du. Paired-domination of trees. J. Global Optim. 25, 1 (2003) 43–54.
  55. A. Rana, A. Pal, M. Pal. An efficient algorithm to solve the distance k-domination problem on permutation graphs, J. Discrete Math. Sci. Cryptogr. 19, 2 (2016), 241–255.
  56. E. Shan, Y. Dong. The k-tuple twin domination in generalized de Bruijn and Kautz networks. Comput. Math. Appl. 63, 1 (2012), 222–227.
  57. P. J. Slater. R-domination in graphs. J. Assoc. Comput. Mach. 23, 2 (1976), 446–450.
  58. D. P. Sumner, P. Blitch. Domination critical graphs. J. Combin. Theory Ser. B 34, 1 (1983), 65–76.
  59. R. Tarjan. Depth-first search and linear graph algorithm. SIAM J. Comput. 1, 2 (1972), 146–160.
  60. L. C. van der Merwe, C. M. Mynhardt, T. W.,Haynes. Criticality index of total domination. Congr. Numer. 131 (1998) 67–73.
  61. M. Yannakakis, F. Gavril. Edge dominating sets in graphs. SIAM J. Appl. Math. 38, 3 (1980), 364–372.