China
Africa
Explore chapters and articles related to this topic
Dominating Set Theory and Algorithms
Published in Jiguo Yu, Xiuzhen Cheng, Honglu Jiang, Dongxiao Yu, Hierarchical Topology Control for Wireless Networks, 2018
Jiguo Yu, Xiuzhen Cheng, Honglu Jiang, Dongxiao Yu
In graph theory, for a graph G = (V, E), the dominating set is a subset D ⊆ V, so that each node v ∊ V satisfies v ∊ D, or at least one neighbor is within D. Dominating number γ(G) is the number of the vertex of the minimum dominating set (MDS) in G. The dominating set problem is to prove whether γ(G) ≤ K exists for K ≤ |V| in G. Garey and Johnson have proven that the dominating set problem is an NP complete problem [1]. If the subgraph introduced from D is connected, D can be regarded as a connected dominating set (CDS). The researchers model the wireless network as the graph G = (V, E), where V is the set of the sensor nodes and E is the set of communication edges among the nodes. Figure 4.1 is a simple instance of the dominating set. The black nodes in the graph form the initial dominating set.
Some New Results on Restrained Edge Domination Number of Graphs
Published in N. P. Shrimali, Nita H. Shah, Recent Advancements in Graph Theory, 2020
A set S⊆ V of vertices in a graph G is called a dominating set if every vertex v ∈ V is either an element of S or is adjacent to an element of S. A dominating set S is a minimal dominating set if no proper subset S′ ⊂ S is a dominating set. The minimum cardinality of a dominating set of G is called domination number, denoted by γ(G) and the corresponding dominating set is called a γ-set of G. A brief account of dominating set and its related concepts can be found in Haynes et al. [7].
Integer linear programming formulations for double roman domination problem
Published in Optimization Methods and Software, 2022
Qingqiong Cai, Neng Fan, Yongtang Shi, Shunyu Yao
A set is called a dominating set if every vertex of G is either in S or adjacent to a vertex of S. The minimum cardinality of a dominating set in G, denoted by , is called the domination number. Domination of graphs has been extensively studied in the scientific literature. The variants of domination have abundant applications, including error-correcting codes constructions for digital communication and efficient data routing in wireless networks [9,10,12,18,28]. Many different kinds of domination arose, such as the connected dominating set [16], the edge dominating set [33], the total domination [24,27], the independent domination [19], Roman domination [32], etc.
Alleviate cascade with fault pair in interdependent smart grid: a communication view
Published in International Journal of Modelling and Simulation, 2018
Kaixuan Wang, Qingtao Zeng, Ningzhe Xing, Shaoyong Guo
Thirdly, double cover for each power node is used to collect fault information reliably. Meanwhile, the path redundancy is necessary for each vertex in the communication network. For each vertex in Gc, as the fourth constraints, there should be two relative independent paths at least. For each power node, there are at least two communication connected nodes in an efficient solution, just as the second constraint has expressed. We can recognize this problem as two dominating set problems. The minimum connected dominating set (MCDS) problem has been proved NP – hard. Moreover, in [31], k connected m dominating set problem is proved to be NP – hard.
An Effective Approach Based on Temporal Centrality Measures for Improving Temporal Network Controllability
Published in Cybernetics and Systems, 2022
Peyman Arebi, Afsaneh Fatemi, Reza Ramezani
The controllability of complex networks was first raised by Liu, Slotine, and Barabási (2011). by combining modern and linear controls. They proposed a method, called structural controllability, in which the MDS is found using the maximum matching theory to control the network. Nacher and Akutsu (2012) showed that the maximum matching theory does not work properly in many networks with very complex structures. Thus, they used an algorithm to find the minimum dominating set to control the network. A minimum dominating set is the smallest subset of nodes such that every node of the network either belongs to this subset or is adjacent to at least one of the nodes in this set (Nacher and Akutsu 2012).