Log in

Relevant bibliographies by topics / K-hop connected dominating set / Journal articles

To see the other types of publications on this topic, follow the link: K-hop connected dominating set.

Journal articles on the topic 'K-hop connected dominating set'

Author: Grafiati

Published: 4 June 2021

Last updated: 11 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'K-hop connected dominating set.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Pabilona, Yamilita M., and Helen M. Rara. "Connected hop domination in graphs under some binary operations." Asian-European Journal of Mathematics 11, no. 05 (October 2018): 1850075. http://dx.doi.org/10.1142/s1793557118500754.

Full text

Abstract:

Let [Formula: see text] be a simple graph. A hop dominating set [Formula: see text] is called a connected hop dominating set of [Formula: see text] if the induced subgraph [Formula: see text] of [Formula: see text] is connected. The smallest cardinality of a connected hop dominating set of [Formula: see text], denoted by [Formula: see text], is called the connected hop domination number of [Formula: see text]. In this paper, we characterize the connected hop dominating sets in the join, corona and lexicographic product of graphs and determine the corresponding connected hop domination number of these graphs. The study of these concepts is motivated with a social network application.

APA, Harvard, Vancouver, ISO, and other styles

2

ZHANG, ZHAO, QINGHAI LIU, and DEYING LI. "TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET." Discrete Mathematics, Algorithms and Applications 01, no. 04 (December 2009): 485–98. http://dx.doi.org/10.1142/s1793830909000361.

Full text

Abstract:

A vertex set D of a connected graph G is a (k, r)-connected dominating set ((k, r)-CDS) if every vertex in V(G)\D is at most r-hops away from at least k vertices in D. Finding a minimum (k, r)-CDS has wireless sensor network as its background. In this paper, we give two approximation algorithms to compute a minimum (k, r)-CDS, which improves previous works in regard of performance ratio.

APA, Harvard, Vancouver, ISO, and other styles

3

LI, DEYING, LIN LIU, and HUIQIANG YANG. "MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS." Discrete Mathematics, Algorithms and Applications 01, no. 01 (March 2009): 45–57. http://dx.doi.org/10.1142/s1793830909000087.

Full text

Abstract:

In this paper, we study the connected r-hop k-dominating set problem in wireless networks. We propose two algorithms for the problem. We prove that algorithm I for UDG has (2r + 1)3 approximate ratio for k ≤ (2r + 1)2 and (2r + 1)((2r + 1)2 + 1)-approximate ratio for k > (2r + 1)2. And algorithm II for any undirected graph has (2r + 1) ln (Δr) approximation ratio, where Δr is the largest cardinality among all r-hop neighborhoods in the network. The simulation results show that our algorithms are efficient.

APA, Harvard, Vancouver, ISO, and other styles

4

Coelho, Rafael S., Phablo F. S. Moura, and Yoshiko Wakabayashi. "The k-hop connected dominating set problem: hardness and polyhedra." Electronic Notes in Discrete Mathematics 50 (December 2015): 59–64. http://dx.doi.org/10.1016/j.endm.2015.07.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Coelho, Rafael S., Phablo F. S. Moura, and Yoshiko Wakabayashi. "The k-hop connected dominating set problem: approximation and hardness." Journal of Combinatorial Optimization 34, no. 4 (March 21, 2017): 1060–83. http://dx.doi.org/10.1007/s10878-017-0128-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Canoy, Jr, Sergio, Reynaldo Villarobe Mollejon, and John Gabriel E. Canoy. "Hop Dominating Sets in Graphs Under Binary Operations." European Journal of Pure and Applied Mathematics 12, no. 4 (October 31, 2019): 1455–63. http://dx.doi.org/10.29020/nybg.ejpam.v12i4.3550.

Full text

Abstract:

Let G be a (simple) connected graph with vertex and edge sets V (G) and E(G),respectively. A set S ⊆ V (G) is a hop dominating set of G if for each v ∈ V (G) \ S, there exists w ∈ S such that dG(v, w) = 2. The minimum cardinality of a hop dominating set of G, denoted by γh(G), is called the hop domination number of G. In this paper we revisit the concept of hop domination, relate it with other domination concepts, and investigate it in graphs resulting from some binary operations.

APA, Harvard, Vancouver, ISO, and other styles

7

Mohamad, Jerson Saguin, and Helen M. Rara. "On Resolving Hop Domination in Graphs." European Journal of Pure and Applied Mathematics 14, no. 3 (August 5, 2021): 1015–23. http://dx.doi.org/10.29020/nybg.ejpam.v14i3.4055.

Full text

Abstract:

A set S of vertices in a connected graph G is a resolving hop dominating set of G if S is a resolving set in G and for every vertex v âˆˆ V (G) \ S there exists u âˆˆ S such that dG(u, v) = 2. The smallest cardinality of such a set S is called the resolving hop domination number of G. This paper presents the characterizations of the resolving hop dominating sets in the join, corona and lexicographic product of two graphs and determines the exact values of their corresponding resolving hop domination number.

APA, Harvard, Vancouver, ISO, and other styles

8

CHEN, YUANZHU PETER, and ARTHUR L. LIESTMAN. "A ZONAL ALGORITHM FOR CLUSTERING AN HOC NETWORKS." International Journal of Foundations of Computer Science 14, no. 02 (April 2003): 305–22. http://dx.doi.org/10.1142/s0129054103001741.

Full text

Abstract:

A Mobile Ad Hoc Network (MANET) is an infrastructureless wireless network that can support highly dynamic mobile units. The multi-hop feature of a MANET suggests the use of clustering to simplify routing. Graph domination can be used in defining clusters in MANETs. A variant of dominating set which is more suitable for clustering MANETs is the weakly-connected dominating set. A cluster is defined to be the set of vertices dominated by a particular vertex in the dominating set. As it is NP-complete to determine whether a given graph has a weakly-connected dominating set of a particular size, we present a zonal distributed algorithm for finding small weakly-connected dominating sets. In this new approach, we divide the graph into regions, construct a weakly-connected dominating set for each region, and make adjustments along the borders of the regions to produce a weakly-connected dominating set of the entire graph. We present experimental evidence that this zonal algorithm has similar performance to and provides better cluster connectivity than previous algorithms.

APA, Harvard, Vancouver, ISO, and other styles

9

Natarajan, C., and S. K. Ayyaswamy. "Hop Domination in Graphs-II." Analele Universitatii "Ovidius" Constanta - Seria Matematica 23, no. 2 (June 1, 2015): 187–99. http://dx.doi.org/10.1515/auom-2015-0036.

Full text

Abstract:

Abstract Let G = (V;E) be a graph. A set S ⊂ V (G) is a hop dominating set of G if for every v ∈ V - S, there exists u ∈ S such that d(u; v) = 2. The minimum cardinality of a hop dominating set of G is called a hop domination number of G and is denoted by γh(G). In this paper we characterize the family of trees and unicyclic graphs for which γh(G) = γt(G) and γh(G) = γc(G) where γt(G) and γc(G) are the total domination and connected domination numbers of G respectively. We then present the strong equality of hop domination and hop independent domination numbers for trees. Hop domination numbers of shadow graph and mycielskian graph of graph are also discussed.

APA, Harvard, Vancouver, ISO, and other styles

10

Bent-Usman, Wardah Masanggila, Rowena Isla, and Sergio Canoy. "Neighborhood Connected k-Fair Domination Under Some Binary Operations." European Journal of Pure and Applied Mathematics 12, no. 3 (August 2, 2019): 1337–49. http://dx.doi.org/10.29020/nybg.ejpam.v12i3.3506.

Full text

Abstract:

Let G=(V(G),E(G)) be a simple graph. A neighborhood connected k-fair dominating set (nckfd-set) is a dominating set S subset V(G) such that |N(u) intersection S|=k for every u is an element of V(G)\S and the induced subgraph of S is connected. In this paper, we introduce and invistigate the notion of neighborhood connected k-fair domination in graphs. We also characterize such dominating sets in the join, corona, lexicographic and cartesians products of graphs and determine the exact value or sharp bounds of their corresponding neighborhood connected k-fair domination number.

APA, Harvard, Vancouver, ISO, and other styles

11

Sun, Yang, and Ma. "Minimum Connected Dominating Set Algorithms for Ad Hoc Sensor Networks." Sensors 19, no. 8 (April 23, 2019): 1919. http://dx.doi.org/10.3390/s19081919.

Full text

Abstract:

To achieve effective communication in ad hoc sensor networks, researchers have been working on finding a minimum connected dominating set (MCDS) as a virtual backbone network in practice. Presently, many approximate algorithms have been proposed to construct MCDS, the best among which is adopting the two-stage idea, that is, to construct a maximum independent set (MIS) firstly and then realize the connectivity through the Steiner tree construction algorithm. For the first stage, this paper proposes an improved collaborative coverage algorithm for solving maximum independent set (IC-MIS), which expands the selection of the dominating point from two-hop neighbor to three-hop neighbor. The coverage efficiency has been improved under the condition of complete coverage. For the second stage, this paper respectively proposes an improved Kruskal–Steiner tree construction algorithm (IK–ST) and a maximum leaf nodes Steiner tree construction algorithm (ML-ST), both of which can make the result closer to the optimal solution. Finally, the simulation results show that the algorithm proposed in this paper is a great improvement over the previous algorithm in optimizing the scale of the connected dominating set (CDS).

APA, Harvard, Vancouver, ISO, and other styles

12

Li, Xiuying, and Zhao Zhang. "Two algorithms for minimum 2-connected r-hop dominating set." Information Processing Letters 110, no. 22 (October 2010): 986–91. http://dx.doi.org/10.1016/j.ipl.2010.08.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Charan Barman, Sambhu, Madhumangal Pal, and Sukumar Mondal. "An $O(n)$-time algorithm to compute minimum $k$-hop connected dominating set of interval graphs." Malaya Journal of Matematik S, no. 1 (2020): 576–80. http://dx.doi.org/10.26637/mjm0s20/0110.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Surendran, Simi, and Sreelakshmy Vijayan. "Distributed Computation of Connected Dominating Set for Multi-Hop Wireless Networks." Procedia Computer Science 63 (2015): 482–87. http://dx.doi.org/10.1016/j.procs.2015.08.372.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Yao, Xiaopeng, Hejiao Huang, and Hongwei Du. "Connected positive influence dominating set in k-regular graph." Discrete Applied Mathematics 287 (December 2020): 65–76. http://dx.doi.org/10.1016/j.dam.2020.08.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Hansberg, Adriana, Bert Randerath, and Lutz Volkmann. "Claw-free graphs with equal 2-domination and domination numbers." Filomat 30, no. 10 (2016): 2795–801. http://dx.doi.org/10.2298/fil1610795h.

Full text

Abstract:

For a graph G a subset D of the vertex set of G is a k-dominating set if every vertex not in D has at least k neighbors in D. The k-domination number k(G) is the minimum cardinality among the k-dominating sets of G. Note that the 1-domination number 1(G) is the usual domination number (G). Fink and Jacobson showed in 1985 that the inequality ?k(G)?(G)+k?2 is valid for every connected graph G. In this paper, we concentrate on the case k = 2, where k can be equal to ?, and we characterize all claw-free graphs and all line graphs G with ?(G) = ?2(G).

APA, Harvard, Vancouver, ISO, and other styles

17

Dai, Fei, and Jie Wu. "On constructing k-connected k-dominating set in wireless ad hoc and sensor networks." Journal of Parallel and Distributed Computing 66, no. 7 (July 2006): 947–58. http://dx.doi.org/10.1016/j.jpdc.2005.12.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

KAMEI, SAYAKA, and HIROTSUGU KAKUGAWA. "A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET." International Journal of Foundations of Computer Science 21, no. 03 (June 2010): 459–76. http://dx.doi.org/10.1142/s0129054110007362.

Full text

Abstract:

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. A self-stabilizing system tolerates any kind and any finite number of transient faults, such as message loss, memory corruption, and topology change. Because such transient faults occur so frequently in mobile ad hoc networks, distributed algorithms on them should tolerate such events. In this paper, we propose a self-stabilizing distributed approximation algorithm for the minimum connected dominating set, which can be used, for example, as a virtual backbone or routing in mobile ad hoc networks. The size of the solution by our algorithm is at most 7.6|Dopt|+1.4, where Dopt is the minimum connected dominating set. The time complexity is O(k) rounds, where k is the depth of input BFS tree.

APA, Harvard, Vancouver, ISO, and other styles

19

Shang, Weiping, Pengjun Wan, Frances Yao, and Xiaodong Hu. "Algorithms for minimum m-connected k-tuple dominating set problem." Theoretical Computer Science 381, no. 1-3 (August 2007): 241–47. http://dx.doi.org/10.1016/j.tcs.2007.04.035.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Nutov, Zeev. "Improved approximation algorithms for k-connected m-dominating set problems." Information Processing Letters 140 (December 2018): 30–33. http://dx.doi.org/10.1016/j.ipl.2018.08.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Pei, Lidan, and Xiangfeng Pan. "The minimum eccentric distance sum of trees with given distance k-domination number." Discrete Mathematics, Algorithms and Applications 12, no. 04 (May 28, 2020): 2050052. http://dx.doi.org/10.1142/s1793830920500524.

Full text

Abstract:

Let [Formula: see text] be a positive integer and [Formula: see text] be a simple connected graph. The eccentric distance sum of [Formula: see text] is defined as [Formula: see text], where [Formula: see text] is the maximum distance from [Formula: see text] to any other vertex and [Formula: see text] is the sum of all distances from [Formula: see text]. A set [Formula: see text] is a distance [Formula: see text]-dominating set of [Formula: see text] if for every vertex [Formula: see text], [Formula: see text] for some vertex [Formula: see text]. The minimum cardinality among all distance [Formula: see text]-dominating sets of [Formula: see text] is called the distance [Formula: see text]-domination number [Formula: see text] of [Formula: see text]. In this paper, the trees among all [Formula: see text]-vertex trees with distance [Formula: see text]-domination number [Formula: see text] having the minimal eccentric distance sum are determined.

APA, Harvard, Vancouver, ISO, and other styles

22

Cáceres, José, Carmen Hernando, Mercè Mora, Ignacio Pelayo, and María Puertas. "Perfect and quasiperfect domination in trees." Applicable Analysis and Discrete Mathematics 10, no. 1 (2016): 46–64. http://dx.doi.org/10.2298/aadm160406007c.

Full text

Abstract:

A k??quasiperfect dominating set of a connected graph G is a vertex subset S such that every vertex not in S is adjacent to at least one and at most k vertices in S. The cardinality of a minimum k-quasiperfect dominating set in G is denoted by ?1k(G). These graph parameters were first introduced by Chellali et al. (2013) as a generalization of both the perfect domination number ?11(G) and the domination number ?(G). The study of the so-called quasiperfect domination chain ?11(G) ? ?12(G)?... ? ?1?(G) = ?(G) enable us to analyze how far minimum dominating sets are from being perfect. In this paper, we provide, for any tree T and any positive integer k, a tight upper bound of ?1k(T). We also prove that there are trees satisfying all possible equalities and inequalities in this chain. Finally a linear algorithm for computing ?1k(T) in any tree T is presented.

APA, Harvard, Vancouver, ISO, and other styles

23

Abdul Gafur, Anuwar Kadir, and Suhadi Wido Saputro. "On Locating-Dominating Set of Regular Graphs." Journal of Mathematics 2021 (September 24, 2021): 1–6. http://dx.doi.org/10.1155/2021/8147514.

Full text

Abstract:

Let G be a simple, connected, and finite graph. For every vertex v ∈ V G , we denote by N G v the set of neighbours of v in G . The locating-dominating number of a graph G is defined as the minimum cardinality of W ⊆ V G such that every two distinct vertices u , v ∈ V G \ W satisfies ∅ ≠ N G u ∩ W ≠ N G v ∩ W ≠ ∅ . A graph G is called k -regular graph if every vertex of G is adjacent to k other vertices of G . In this paper, we determine the locating-dominating number of k -regular graph of order n , where k = n − 2 or k = n − 3 .

APA, Harvard, Vancouver, ISO, and other styles

24

Du, Hongwei, Caiwei Yuan, He Yuan, Shanshan Wei, and Wen Xu. "Identify Connected Positive Influence Dominating Set in Social Networks Using Two-Hop Coverage." IEEE Transactions on Computational Social Systems 6, no. 5 (October 2019): 956–67. http://dx.doi.org/10.1109/tcss.2019.2937396.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Gao, Xiaofeng, Wei Wang, Zhao Zhang, Shiwei Zhu, and Weili Wu. "A PTAS for minimum d-hop connected dominating set in growth-bounded graphs." Optimization Letters 4, no. 3 (October 9, 2009): 321–33. http://dx.doi.org/10.1007/s11590-009-0148-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Zhang, Zhao, Jiao Zhou, Shaojie Tang, Xiaohui Huang, and Ding-Zhu Du. "Computing Minimum k-Connected m-Fold Dominating Set in General Graphs." INFORMS Journal on Computing 30, no. 2 (May 2018): 217–24. http://dx.doi.org/10.1287/ijoc.2017.0776.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Ma, Wenkai, Deying Li, and Zhao Zhang. "Algorithms for the minimum weight k-fold (connected) dominating set problem." Journal of Combinatorial Optimization 23, no. 4 (December 3, 2010): 528–40. http://dx.doi.org/10.1007/s10878-010-9372-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

WANG, HAICHAO, and LIYING KANG. "MATCHING PROPERTIES IN DOUBLE DOMINATION EDGE CRITICAL GRAPHS." Discrete Mathematics, Algorithms and Applications 02, no. 02 (June 2010): 151–60. http://dx.doi.org/10.1142/s1793830910000541.

Full text

Abstract:

A vertex subset S of a graph G = (V, E) is a double dominating set for G if |N[v]∩S| ≥ 2 for each vertex v ∈ V, where N[v] = {u |uv ∈ E}∪{v}. The double domination number of G, denoted by γ×2(G), is the cardinality of a smallest double dominating set of G. A graph G is said to be double domination edge critical if γ×2(G + e) < γ×2(G) for any edge e ∉ E. A double domination edge critical graph G with γ×2(G) = k is called k - γ×2(G)-critical. In this paper, we first show that G has a perfect matching if G is a connected 3 - γ×2(G)-critical graph of even order. Secondly, we show that G is factor-critical if G is a connected 3 - γ×2(G)-critical graph with odd order and minimum degree at least 2. Finally, we show that G is factor-critical if G is a connected K1,4-free 4 - γ×2(G)-critical graph of odd order with minimum degree at least 2.

APA, Harvard, Vancouver, ISO, and other styles

29

Liang, Jiarong, Meng Yi, Yanyan Li, and Xinyu Liang. "The Construction of a Virtual Backbone with a Bounded Diameter in a Wireless Network." Wireless Communications and Mobile Computing 2020 (July 4, 2020): 1–14. http://dx.doi.org/10.1155/2020/5602325.

Full text

Abstract:

We usually use a digraph to represent a wireless network (WN). Correspondingly, a connected dominating set (CDS) of the digraph is usually used to denote a virtual backbone (VB) of the corresponding WN. In this article, focusing on the problem of a minimum strongly connected dominating and absorbing set (MSCDAS) with a bounded diameter (or guaranteed routing cost) for a digraph, which is strongly connected, we introduce two algorithms. One is called the guaranteed routing cost strongly connected dominating and absorbing set (GOC-SCDAS), which can generate a strongly connected dominating and absorbing set (SCDAS) with a performance ratio 14.4k+1/22 in respect of the optimal solution. Another is called the α guaranteed routing cost strongly connected bidirectional dominating and absorbing set (α-GOC-SCBDAS), which can generate a strongly connected bidirectional dominating and absorbing set (SCBDAS) with a performance ratio 8.8443k+1/22k+1/22 in respect of the optimal solution and a better routing cost, where k=rmax/rmin and rmin,rmax is the transmission range of nodes in the network. Through the simulation experiments, we obtain the conclusion that in terms of the diameter and average routing path length (ARPL) of CDS, the outputs of our algorithms are better than those of the algorithm in (Du et al. 2006).

APA, Harvard, Vancouver, ISO, and other styles

30

CARO, YAIR, and RAPHAEL YUSTER. "Dominating a Family of Graphs with Small Connected Subgraphs." Combinatorics, Probability and Computing 9, no. 4 (July 2000): 309–13. http://dx.doi.org/10.1017/s0963548300004260.

Full text

Abstract:

Let F = {G1, …, Gt} be a family of n-vertex graphs defined on the same vertex-set V, and let k be a positive integer. A subset of vertices D ⊂ V is called an (F, k)-core if, for each v ∈ V and for each i = 1, …, t, there are at least k neighbours of v in Gi that belong to D. The subset D is called a connected (F, k)-core if the subgraph induced by D in each Gi is connected. Let δi be the minimum degree of Gi and let δ(F) = minti=1δi. Clearly, an (F, k)-core exists if and only if δ(F) [ges ] k, and a connected (F, k)-core exists if and only if δ(F) [ges ] k and each Gi is connected. Let c(k, F) and cc(k, F) be the minimum size of an (F, k)-core and a connected (F, k)-core, respectively. The following asymptotic results are proved for every t < ln ln δ and k < √lnδ:formula hereThe results are asymptotically tight for infinitely many families F. The results unify and extend related results on dominating sets, strong dominating sets and connected dominating sets.

APA, Harvard, Vancouver, ISO, and other styles

31

Liang, Jiarong, Meng Yi, Weiguang Zhang, Yanyan Li, Xinyu Liang, and Bin Qin. "On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks." Complexity 2020 (February 24, 2020): 1–12. http://dx.doi.org/10.1155/2020/9189645.

Full text

Abstract:

In a wireless ad hoc network, the size of the virtual backbone (VB) is an important factor for measuring the quality of the VB. The smaller the VB is, the less the overhead caused by the VB. Since ball graphs (BGs) have been used to model 3-dimensional wireless ad hoc networks and since a connected dominating set can be used to represent a VB undertaking routing-related tasks, the problem of finding the smallest VB is transformed into the problem of finding a minimum connected dominating set (MCDS). Many research results on the MCDS problem have been obtained for unit disk graphs and unit ball graphs, in which the transmission ranges of all nodes are identical. In some situations, the node powers can vary. One can model such a network as a graph with different transmission ranges for different nodes. In this paper, we focus on the problem of minimum strongly connected dominating and absorbing sets (MSCDASs) in a strongly connected directed ball graph with different transmission ranges, which is also NP-hard. We design an algorithm considering the construction of a strongly connected dominating and absorbing set (SCDAS), whose size does not exceed 319/15k3+116/5k2+29/5kopt+29/3k3+116/5k2+87/5k+13/15, where opt is the size of an MCDAS and k denotes the ratio of rmax to rmin in the ad hoc network with transmission range rmin,rmax. Our simulations show the feasibility of the algorithm proposed in this paper.

APA, Harvard, Vancouver, ISO, and other styles

32

P. S., Vinayagam. "A Fault-tolerant Improved OLSR Protocol using k-Connected m-Dominating Set." International Journal of Computer Network and Information Security 9, no. 12 (December 8, 2017): 55–63. http://dx.doi.org/10.5815/ijcnis.2017.12.07.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Shang, Weiping, Frances Yao, Pengjun Wan, and Xiaodong Hu. "On minimum m-connected k-dominating set problem in unit disc graphs." Journal of Combinatorial Optimization 16, no. 2 (December 5, 2007): 99–106. http://dx.doi.org/10.1007/s10878-007-9124-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Li, Ke, Xiaofeng Gao, Fan Wu, and Guihai Chen. "A Constant Factor Approximation for $d$ -Hop Connected Dominating Set in Three-Dimensional Wireless Networks." IEEE Transactions on Wireless Communications 18, no. 9 (September 2019): 4357–67. http://dx.doi.org/10.1109/twc.2019.2923744.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Shan, N. A., Weili Wu, Wei Wang, Hongjie Du, Xiaofeng Gao, and Ailian Jiang. "Constructing minimum interference connected dominating set for multi-channel multi-radio multi-hop wireless network." International Journal of Sensor Networks 11, no. 2 (2012): 100. http://dx.doi.org/10.1504/ijsnet.2012.045961.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Mohanty, Jasaswi Prasad, Chittaranjan Mandal, and Chris Reade. "Distributed construction of minimum Connected Dominating Set in wireless sensor network using two-hop information." Computer Networks 123 (August 2017): 137–52. http://dx.doi.org/10.1016/j.comnet.2017.05.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Ali Zardari, Zulfiqar, Jingsha He, Nafei Zhu, Khalid Mohammadani, Muhammad Pathan, Muhammad Hussain, and Muhammad Memon. "A Dual Attack Detection Technique to Identify Black and Gray Hole Attacks Using an Intrusion Detection System and a Connected Dominating Set in MANETs." Future Internet 11, no. 3 (March 5, 2019): 61. http://dx.doi.org/10.3390/fi11030061.

Full text

Abstract:

A mobile ad-hoc network (MANET) is a temporary network of wireless mobile nodes. In a MANET, it is assumed that all of the nodes cooperate with each other to transfer data packets in a multi-hop fashion. However, some malicious nodes don’t cooperate with other nodes and disturb the network through false routing information. In this paper, we propose a prominent technique, called dual attack detection for black and gray hole attacks (DDBG), for MANETs. The proposed DDBG technique selects the intrusion detection system (IDS) node using the connected dominating set (CDS) technique with two additional features; the energy and its nonexistence in the blacklist are also checked before putting the nodes into the IDS set. The CDS is an effective, distinguished, and localized approach for detecting nearly-connected dominating sets of nodes in a small range in mobile ad hoc networks. The selected IDS nodes broadcast a kind of status packet within a size of the dominating set for retrieving the complete behavioral information from their nodes. Later, IDS nodes use our DDBG technique to analyze the collected behavioral information to detect the malicious nodes and add them to the blacklist if the behavior of the node is suspicious. Our experimental results show that the quality of the service parameters of the proposed technique outperforms the existing routing schemes.

APA, Harvard, Vancouver, ISO, and other styles

38

Kumar, Gulshan, Mritunjay Kumar Rai, Rahul Saha, and Hye-jin Kim. "An improved DV-Hop localization with minimum connected dominating set for mobile nodes in wireless sensor networks." International Journal of Distributed Sensor Networks 14, no. 1 (January 2018): 155014771875563. http://dx.doi.org/10.1177/1550147718755636.

Full text

Abstract:

Localization is one of the key concepts in wireless sensor networks. Different techniques and measures to calculate the location of unknown nodes were introduced in recent past. But the issue of nodes’ mobility requires more attention. The algorithms introduced earlier to support mobility lack the utilization of the anchor nodes’ privileges. Therefore, in this article, an improved DV-Hop localization algorithm is introduced that supports the mobility of anchor nodes as well as unknown nodes. Coordination of anchor nodes creates a minimum connected dominating set that works as a backbone in the proposed algorithm. The focus of the research paper is to locate unknown nodes with the help of anchor nodes by utilizing the network resources efficiently. The simulated results in network simulator-2 and the statistical analysis of the data provide a clear impression that our novel algorithm improves the error rate and the time consumption.

APA, Harvard, Vancouver, ISO, and other styles

39

WILLSON, JAMES K., XIAOFENG GAO, ZHONGHUA QU, YI ZHU, YINGSHU LI, and WEILI WU. "EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS." Discrete Mathematics, Algorithms and Applications 01, no. 04 (December 2009): 437–61. http://dx.doi.org/10.1142/s1793830909000348.

Full text

Abstract:

A Connected Dominating Set (CDS) can be used to construct a virtual backbone for wireless and mobile ad-hoc networks to make the system hierarchical and efficient. A virtual backbone can significantly improve network throughput, optimize broadband utilization, extend network lifetime, and reduce interference as well as packet retransmissions. Calculating a minimum backbone for a network is critical to reduce routing computation and energy consumption. This problem is a well-known NP-hard optimization problem, which has various applications in practice. In this paper, we propose a new problem based on customer fairness, which looks for a minimum CDS in a given communication model with shortest path constraints. It guarantees that any two clients can communicate with each other through this CDS with hop counts the same as the best path from the original graph, which means that routing on such a CDS will not bring additional traffic for every client. We name this problem as shortest path connected dominating set (SPCDS) and prove its NP-hardness by reduction from Hitting Set. Then we propose a centralized greedy algorithm and an efficient distributed approximation algorithm with approximation ratio Δ to solve SPCDS, where Δ is the maximum vertex degree in the given topology. We also analyze the time complexity, message complexity, and evaluate the efficiency of our distributed heuristic by several numerical experiments and comparisons with previous literatures.

APA, Harvard, Vancouver, ISO, and other styles

40

Fujita, Satoshi. "On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs." International Journal of Foundations of Computer Science 27, no. 07 (November 2016): 829–43. http://dx.doi.org/10.1142/s0129054116500325.

Full text

Abstract:

A connected dominating set (CDS, for short) for graph G is a dominating set which induces a connected subgraph of G. In this paper, we consider the problem of finding a minimum CDS for unit disk graphs, which have recently attracted considerable attention as a model of virtual backbone in multi-hop wireless networks. This optimization problem is known to be NP-hard and many approximation algorithms have been proposed in the literature. This paper proves a lower bound on the performance ratio of a greedy algorithm of Guha and Khuller which was originally proposed for general graphs and is known to be a representative in which the lookahead plays a crucial role in selecting a vertex to be contained in the CDS. More specifically, we show that for any fixed ε>0 and integer n0≥1, there is a unit disk graph with bounded degree consisting of at least n0 vertices for which the output of the greedy algorithm is no better than 3−ε times of an optimum solution to the same graph.

APA, Harvard, Vancouver, ISO, and other styles

41

Moghaddam, Sogand Sahabi, and Abbas Karimi. "Multicast Data Replication Approach for Improving Fault Tolerance in Mobile Ad hoc Networks." Ciência e Natura 37 (December 19, 2015): 399. http://dx.doi.org/10.5902/2179460x20801.

Full text

Abstract:

Multicast data replication provides a possible solution for improving data accessibility in highly dynamic and fault prone mobile ad hoc environments. Our novel multicast data replication approach operates in a self-organizing manner where the network nodes that has unit host detector construct a connected dominating set (CDS) based on the topology graph by collecting information from neighboring nodes using multicast if gathered data from neighbors have two non-adjacent neighbors then use that virtual backbone for efficient data replication, data search and routing. In this study, we compare our proposed approach with SCALAR and evaluate it in average hop counts and successful delivery ratio with different node numbers and speeds.It is shown that the average hop counts increased but with falling rate and 20 percent successful delivery ratio is achieved, so it is demonstrated that PM act with respect to fault tolerance improvement, power consumption and load balancing is occurred.

APA, Harvard, Vancouver, ISO, and other styles

42

Ahn, Namsu, and Sungsoo Park. "An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks." Wireless Networks 21, no. 3 (September 24, 2014): 783–92. http://dx.doi.org/10.1007/s11276-014-0819-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Habib, Sami J., and Paulvanna N. Marimuthu. "Management Scheme for Data Collection within Wireless Sensor Networks." International Journal of Adaptive, Resilient and Autonomic Systems 3, no. 2 (April 2012): 59–76. http://dx.doi.org/10.4018/jaras.2012040104.

Full text

Abstract:

This paper proposes a data management scheme which employs an energy constrained algorithm selecting between direct and multi-hop transmissions autonomously based on the residual energy level of the individual sensors. The proposed data management scheme rules out the selection of hotspot sensors, the sensors located closer to the base stations, as the intermediate sensors to avoid the dying of these sensors. In each data transmission, the scheme selects one of the neighborhood sensors having minimal Euclidean distance and maximum energy-level as the intermediate node from the neighboring set, without repeating the selection. The proposed data management scheme manages the data collection by utilizing two scheduling algorithms; as soon as possible (ASAP) and as late as possible (ALAP). As a measure of performance, the simulation results of the data management scheme have been compared with that of minimum connected dominating set algorithm (MCDS). The simulation results demonstrate that the data management scheme outperforms with respect to consume less energy; moreover, it can be observed that the scheme finishes an overall short waiting time of the selected sensors compared to the direct transmission in transmitting the data to the base station. The robustness of the proposed scheme is tested by varying the network sizes and varying the sensing radii.

APA, Harvard, Vancouver, ISO, and other styles

44

Barman, Sambhu Charan, Madhumangal Pal, and Sukumar Mondal. "An optimal algorithm to find minimum k-hop dominating set of interval graphs." Discrete Mathematics, Algorithms and Applications 11, no. 02 (April 2019): 1950016. http://dx.doi.org/10.1142/s1793830919500162.

Full text

Abstract:

For a fixed positive integer [Formula: see text], a [Formula: see text]-hop dominating set [Formula: see text] of a graph [Formula: see text] is a subset of [Formula: see text] such that every vertex [Formula: see text] is within [Formula: see text]-steps from at least one vertex [Formula: see text], i.e., [Formula: see text]. A [Formula: see text]-hop dominating set [Formula: see text] is said to be minimal if there does not exist any [Formula: see text] such that [Formula: see text] is a [Formula: see text]-hop dominating set of G. A dominating set [Formula: see text] is said to be minimum [Formula: see text]-hop dominating set, if it is minimal as well as it is [Formula: see text]-hop dominating set. In this paper, we present an optimal algorithm to find a minimum [Formula: see text]-hop dominating set of interval graphs with [Formula: see text] vertices which runs in [Formula: see text] time.

APA, Harvard, Vancouver, ISO, and other styles

45

Ha, Deok-Kyu, Young-Jun Song, Dong-Woo Kim, Young-Joon Kim, and In-Sung Lee. "Power, Degree and Selection Information-Aware Connected Dominating Set Construction Algorithm in Ad-hoc Wireless Networks." Journal of the Korea Contents Association 9, no. 8 (August 28, 2009): 49–56. http://dx.doi.org/10.5392/jkca.2009.9.8.049.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Yadav, Anil Kumar, Rama Shankar Yadav, Raghuraj Singh, and Ashutosh Kumar Singh. "Connected dominating set for wireless ad hoc networks: a survey." International Journal of Engineering Systems Modelling and Simulation 7, no. 1 (2015): 22. http://dx.doi.org/10.1504/ijesms.2015.066127.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Han, Bo, and Weijia Jia. "Clustering wireless ad hoc networks with weakly connected dominating set." Journal of Parallel and Distributed Computing 67, no. 6 (June 2007): 727–37. http://dx.doi.org/10.1016/j.jpdc.2007.03.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Avula, Mallikarjun. "Constructing Minimum Connected Dominating Set in Mobile Ad Hoc Networks." International Journal on Applications of Graph Theory In wireless Ad Hoc Networks And sensor Networks 4, no. 2 (September 30, 2012): 15–27. http://dx.doi.org/10.5121/jgraphoc.2012.4202.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

WU, JIE, and FEI DAI. "ON LOCALITY OF DOMINATING SET IN AD HOC NETWORKS WITH SWITCH-ON/OFF OPERATIONS." Journal of Interconnection Networks 03, no. 03n04 (September 2002): 129–47. http://dx.doi.org/10.1142/s0219265902000598.

Full text

Abstract:

Efficient routing among a set of mobile hosts is one of the most important functions in ad hoc wireless networks. Routing based on a connected dominating set is a promising approach, where the search space for a route is reduced to the hosts in the set. A set is dominating if all the hosts in the system are either in the system are either in the set or neighbors of hosts in the set. In this paper, we first review a distributed formation of a connected dominating set called marking process and dominating-set-based routing. Then we propose several ways to reduce the size of the dominating set and study the locality of dominating set and study the locality of dominating set in ad hoc wireless networks with switch-on/off operations. Results show that the dominating set derived from the marking process exhibits good locality properties; i.e., the change of a host status, gateway (dominating) or non-gateway (dominated), affects only the status of hosts in a restricted vicinity. In addition, locality of host status updated is also verified through simulation.

APA, Harvard, Vancouver, ISO, and other styles

50

Sharmila. "CONSTRUCTION OF STRATEGIC CONNECTED DOMINATING SET FOR MOBILE AD HOC NETWORKS." Journal of Computer Science 10, no. 2 (February 1, 2014): 285–95. http://dx.doi.org/10.3844/jcssp.2014.285.295.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!