Computation of minimum $d$-hop connected dominating set of trees in $O(n)$ time
DOI:
https://doi.org/10.13069/jacodesmath.v9i3.160Keywords:
$D$-hop connected domination, Domination number, TreesAbstract
For a graph $G=(V,E)$ and a fixed constant $d\in \mathbb{N}$, a subset $D_{hd}$ of the vertex set $V$ is a $d$-hop connected dominating set of the graph $G$ if each vertex $t\in V$ is situated at most $d$-steps from at least one vertex $z\in D_{hd}$, that is, $d(t,z)\leq d$, and the subgraph of $G$ induced by $D_{hd}$ is connected. If $D_{hd}$ has minimum cardinality, then it is a minimum $d$-hop connected dominating set. In this paper, we present two $O(n)$-time algorithms for computing a minimum $D_{hd}$ of trees with $n$ vertices. We also design an algorithm to find the central vertices of a tree. Besides that, we also study some properties related to hop-domination on trees.
Received: 4 September 2020 | Accepted: 7 May 2022Downloads
References
A. S. Adhya, S. Mondal, and S. C. Barman, An optimal algorithm to find minimum $k$-hop connected dominating set of permutation graphs, Asian-Eur. J. Math. 14(4) (2021) 2150049.
B. Awerbuch and D. Peleg, Sparse partitions, in: 31st Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1990, pp. 503–513.
S. K. Ayyaswamy, B. Krishnakumari, C. Natarajan, and Y. B. Venkatakrishnan, Bounds on the hop domination number of a tree, Proc. Math. Sci. 125(4) (2015) 449–455.
S. C. Barman, M. Pal, and S. Mondal, An optimal algorithm to find minimum $k$-hop dominating set of interval graphs, Discrete Math. Algorithms Appl. 11(2) (2019) 1950016.
P. Basuchowdhuri and S. Majumder, Finding influential nodes in social networks using minimum $k$-hop dominating set, in: Applied Algorithms, Lecture Notes in Computer Science, Vol. 8321, Springer, Cham, 2014, pp. 137–151.
D. A. Benson, M. S. Boguski, D. J. Lipman, J. Ostell, B. F. Ouellette, B. A. Rapp, and D. L. Wheeler, GenBank, Nucleic Acids Res. 27(1) (1999) 12–17.
S. Berchtold, D. Keim, and H. P. Kriegel, The X-tree: An index structure for high-dimensional data, in: Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB 1996), Morgan Kaufmann, 1996, pp. 28–39.
C. Berge, The Theory of Graphs and its Applications, translated by A. Doig, Methuen & Co., London, 1962.
A. Cayley, On the theory of the analytical forms called trees, Philos. Mag. 13(85) (1857) 172–176.
G. J. Chang, Algorithmic aspects of domination in graphs, in: P. M. Pardalos and D.-Z. Du (Eds.), Handbook of Combinatorial Optimization, 2nd ed., Springer, New York, 2013, pp. 339–405.
H. S. Chao, F. R. Hsu, and 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.
C. C. Y. Chen and S. K. Das, Breadth-first traversal of trees and integer sorting in parallel, Inf. Process. Lett. 41(1) (1992) 39–49.
E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, Total domination in graphs, Networks 10(3) (1980) 211–219.
D. Cokuslu and K. Erciyes, A hierarchical connected dominating set based clustering algorithm for mobile ad hoc networks, in: 15th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS 2007), IEEE, 2007, pp. 60–66.
A. D’Atri and M. Moscarini, Distance-hereditary graphs, Steiner trees, and connected domination, SIAM J. Comput. 17(3) (1988) 521–538.
E. D. Demaine, M. Hajiaghayi, and D. M. Thilikos, Fixed-parameter algorithms for $(k,r)$-center in planar graphs and map graphs, ACM Trans. Algorithms 1(1) (2005) 33–47.
P. Dorbec, M. A. Henning, M. Montassier, and J. Southey, Independent domination in cubic graphs, J. Graph Theory 80(4) (2015) 329–349.
O. Favaron, M. A. Henning, C. M. Mynhardt, and J. Puech, Total domination in graphs with minimum degree three, J. Graph Theory 34(1) (2000) 9–19.
X. Gao, W. Wu, X. Zhang, and X. Li, A constant-factor approximation for $d$-hop connected dominating sets in unit disk graph, Int. J. Sens. Netw. 12(3) (2012) 125–136.
F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
S. T. Hedetniemi and R. Laskar (Eds.), Topics on Domination, Annals of Discrete Mathematics, Vol. 48, North-Holland, Amsterdam, 1991.
S. Kundu and S. Majumder, A linear time algorithm for optimal $k$-hop dominating set of a tree, Inf. Process. Lett. 116(2) (2016) 197–202.
B. D. McKay, On the spectral characterisation of trees, Ars Combin. 3 (1977) 219–232.
C. Natarajan and S. K. Ayyaswamy, Hop domination in graphs-II, An. Ştiinţ. Univ. Ovidius Constanţa Ser. Mat. 23(2) (2015) 187–199.
T. N. Nguyen and D. T. Huynh, Connected $d$-hop dominating sets in mobile ad hoc networks, in: 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt 2006), IEEE, 2006, pp. 1–8.
O. Ore, Theory of Graphs, American Mathematical Society Colloquium Publications, Vol. 38, American Mathematical Society, Providence, RI, 1962.
A. Rana, A. Pal, and 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.
M. Q. Rieck, S. Pai, and S. Dhar, Distributed routing algorithms for multi-hop ad hoc networks using $d$-hop connected $d$-dominating sets, Comput. Netw. 47(6) (2005) 785–799.
E. Sampathkumar and H. B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13(6) (1979) 607–613.
R. S. Shaheen, Bounds for the 2-domination number of toroidal grid graphs, Int. J. Comput. Math. 86(4) (2009) 584–588.
P. J. Slater, $R$-domination in graphs, J. ACM 23(3) (1976) 446–450.
D. P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory Ser. B 34(1) (1983) 65–76.
L. K. Swift, T. Johnson, and P. E. Livadas, Parallel creation of linear octrees from quadtree slices, Parallel Process. Lett. 4(4) (1994) 447–453.
L. C. van der Merwe, C. M. Mynhardt, and T. W. Haynes, Criticality index of total domination, Congr. Numer. 131 (1998) 67–73.
L. C. van der Merwe, C. M. Mynhardt, and T. W. Haynes, Total domination edge critical graphs, Utilitas Math. 54 (1998) 229–240.
L. C. van der Merwe, C. M. Mynhardt, and T. W. Haynes, Total domination edge critical graphs with maximum diameter, Discuss. Math. Graph Theory 21(2) (2001) 187–205.
T. H. P. Vuong and D. T. Huynh, Adapting $d$-hop dominating sets to topology changes in ad hoc networks, in: Proceedings Ninth International Conference on Computer Communications and Networks (ICCCN 2000), IEEE, 2000, pp. 348–353.
A. K. Yadav, R. S. Yadav, R. Singh, and A. K. Singh, Connected dominating set for wireless ad hoc networks: A survey, Int. J. Eng. Syst. Model. Simul. 7(1) (2015) 22–34.
S. Yau and W. Gao, Multi-hop clustering based on neighborhood benchmark in mobile ad-hoc networks, Mob. Netw. Appl. 12(5-6) (2007) 381–391.
J. Yu, N. Wang, G. Wang, and D. Yu, Connected dominating sets in wireless ad hoc and sensor networks – A comprehensive survey, Comput. Commun. 36(2) (2013) 121–134.
